#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#define deb(...) logger(#__VA_ARGS__, __VA_ARGS__)
template<typename ...Args>
void logger(string vars, Args&&... values) {
cerr<<vars<<" = ";
string delim="";
(...,(cerr<<delim<<values,delim=", "));
cerr<<"\n";
}
#else
#define deb(...) logger(#__VA_ARGS__, __VA_ARGS__)
template<typename ...Args>
void logger(string vars, Args&&... values) {}
#endif
#define pb push_back
#define sz(x) (int)(x.size())
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
template<typename T> inline void maxa(T& a,T b){a=max(a,b);}
template<typename T> inline void mina(T& a,T b){a=min(a,b);}
const int mxN=15e2+5;
int uf[mxN],num,cnt[mxN],N,done;
int find(int x){return uf[x]<0?x:uf[x]=find(uf[x]);}
bool same(int x,int y){return find(x)==find(y);}
void unite(int x,int y){
x=find(x); y=find(y);
assert(x!=y);
if(uf[x]>uf[y])
swap(x,y);
uf[x]+=uf[y]; uf[y]=x;
num--;
}
int hasEdge(int u,int v){
cnt[u]++; cnt[v]++;
if(cnt[u]==N-1)
done++;
if(cnt[v]==N-1)
done++;
if(num==2)
return 0;
if(same(u,v))
return 0;
if(cnt[u]==N-1 && abs(uf[find(u)])==1){
unite(u,v);
return 1;
}
if(cnt[v]==N-1 && abs(uf[find(v)])==1){
unite(u,v);
return 1;
}
if(num+done>N){
unite(u,v);
return 1;
}
return 0;
}
void initialize(int n){
memset(uf,-1,sizeof(uf));
num=n; N=n;
}
