#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) { /// daca am cnt > 1, pot sa nu le unesc si practic judge-ul nu afla nimic.
/// Pentru a fi graful conex, trebuie sa unesc u si v, dar eu inca mai am niste variante de muchii cu care le pot uni.
/// Astfel, judge-ul prin intrebarea asta nu afla nimic sigur, graful putand fi ori conex ori sa nu fie conex(asta stie doar cand ajunge la ultima muchie ce poate uni u si v si afla daca exista sau nu).
/// E clar de aici ca jocul ce il simulam pentru a avea o strategie sigura de castig
/// are la baza un graf conex(daca nu ar fi conex, judge-ul ar putea afla mai repede ca nu poate uni 2
/// componente de pe parcurs si ar sti la un pas i < r ca graful nu e conex, deci am pierde).
/// Prin prisma faptului ca 2 componente de pe parcurs sunt unite doar
/// in momentul in care mai exista o unica muchie ce le poate uni,
/// inductiv, realizam ca judge-ul va afla ca graful este conex doar la intrebarea r,
/// cand va uni ultimele 2 componente ramase cu singura muchie ramasa ce le poate uni, deci va pierde mereu.
--cnt[u][v], --cnt[v][u];
return 0;
}
/// Aici pe langa muchiile ce unesc 2 componente mai trasez si alea
/// ce au capetele in 2 noduri din aceeasi componenta, dar asta nu este obligatoriu
/// ele fiind irelevante pentru continuitatea jocului in acest punct.
unite(u, v);
return 1;
}
