#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(long long i=0;i<(long long)(n);i++)
#define REP(i,k,n) for(long long i=k;i<(long long)(n);i++)
#define all(a) a.begin(),a.end()
#define rsort(a) {sort(all(a));reverse(all(a));}
#define pb emplace_back
#define lb(v,k) (lower_bound(all(v),(k))-v.begin())
#define fi first
#define se second
#define dupli(a) {sort(all(a));a.erase(unique(all(a)),a.end());}
#define dame(a) {cout<<a<<endl;return 0;}
typedef long long ll;
typedef pair<ll,ll> P;
typedef tuple<ll,ll,ll> PP;
using vi=vector<ll>;
using vvi=vector<vi>;
using vvvi=vector<vvi>;
using vp=vector<P>;
using vvp=vector<vp>;
using vvvp=vector<vvp>;
using vb=vector<bool>;
template<class T> bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;}
template<class T> bool chmax(T&a,T b){if(a<b){a=b;return true;}return false;}
template<class T> void out(T a){cout<<a<<'\n';}
template<class T> void outp(T a){cout<<'('<<a.fi<<','<<a.se<<')'<<'\n';}
template<class T> void outvp(T v){rep(i,v.size())cout<<'('<<v[i].fi<<','<<v[i].se<<')';cout<<'\n';}
template<class T> void outvvp(T v){rep(i,v.size())outvp(v[i]);}
template<class T> void outv(T v){rep(i,v.size()){if(i)cout<<' ';cout<<v[i];}cout<<'\n';}
template<class T> void outvv(T v){rep(i,v.size())outv(v[i]);}
const ll inf=1001001001001001001;
vvi g;
int n;
class UF{
public:
vi data;stack<P> st;
UF(ll N){
data=vi(N,1);
}
bool heigou(ll x,ll y,bool undo=false){
x=root(x);y=root(y);
if(data[x]>data[y])swap(x,y);
if(undo){st.emplace(y,data[y]);st.emplace(x,data[x]);}
if(x==y)return false;
rep(i,n)if(root(i)==i){
g[i][y]+=g[i][x];
g[y][i]+=g[i][x];
}
data[y]+=data[x];data[x]=-y;
return true;
}
ll root(ll i){if(data[i]>0)return i;return root(-data[i]);}
ll getsize(ll i){return data[root(i)];}
bool same(ll a,ll b){return root(a)==root(b);}
void undo(){rep(i,2){data[st.top().fi]=st.top().se;st.pop();}}
};
UF uf(0);
void initialize(int N){
n=N;g=vvi(n,vi(n));uf=UF(n);
}
int hasEdge(int a,int b){
a=uf.root(a);b=uf.root(b);
if(g[a][b]==uf.getsize(a)*uf.getsize(b)-1){
uf.heigou(a,b);return 1;
}
else{
g[a][b]++;g[b][a]++;return 0;
}
}
/*
int main(){
ll n;cin>>n;
initialize(n);
rep(i,n*(n-1)/2){
ll a,b;cin>>a>>b;
out(hasEdge(a,b));
}
}*/
