#include <bits/stdc++.h>
using namespace std;
const int NMAX = 1505;
int N, p[NMAX], sz[NMAX], cnt[NMAX][NMAX];
int get(int x) {
if(x == p[x])
return x;
return p[x] = get(p[x]);
}
void unite(int u, int v) {
if(u == v)
return;
if(sz[u] < sz[v])
swap(u, v);
for(int k = 1; k <= N; ++k)
cnt[u][k] += cnt[v][k], cnt[k][u] += cnt[v][k];
cnt[u][v] = cnt[v][u] = 0;
p[v] = u;
}
void initialize(int n) {
N = n;
for(int i = 1; i <= N; ++i) {
p[i] = i;
sz[i] = 1;
for(int j = 1; j <= N; ++j)
if(i != j)
cnt[i][j] = 1;
}
}
int hasEdge(int u, int v) {
++u, ++v;
u = get(u);
v = get(v);
if(cnt[u][v] > 1) {
--cnt[u][v], --cnt[v][u];
return 0;
}
unite(u, v);
return 1;
}
