// Skyqwq
#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define mp make_pair
#define pb push_back

typedef long long LL;
typedef pair<int, int> PII;


template <typename T> bool inline chkMin(T &x, T y) { return y < x ? x = y, 1 : 0; }
template <typename T> bool inline chkMax(T &x, T y) { return y > x ? x = y, 1 : 0; }

#include "game.h"

const int N = 1505;

int f[N], n, g[N][N], t, w[N][N], sz[N];

PII e[N * N];

int find(int x) {
    return x == f[x] ? x : f[x] = find(f[x]);
}

bool merge(int x, int y) {
    x = find(x), y = find(y);
    if (x == y) return 0;
    f[x] = y; sz[y] += sz[x];
    for (int i = 1; i <= n; i++) {
        w[y][i] += w[x][i];
    }
    for (int i = 1; i <= n; i++) {
        if (find(i) == i && i != x && i != y) {
            w[i][y] += w[i][x];
        }
    }
    return 1;
}

void initialize(int nt) {
    n = nt; t = 0;
    for (int i = 1; i <= n; i++) f[i] = i, sz[i] = 1;
}

void inline apd(int x, int y) {
    x = find(x);
    if (find(y) != x)
        w[x][find(y)]++;
}

bool inline chk(int x, int y) {
    x = find(x), y = find(y);
    if (x == y) return 0;
    int ct = w[x][y];
    return ct + 1 == sz[x] * sz[y];
}

int hasEdge(int u, int v) {
    ++u, ++v;
    if (chk(u, v)) {
        merge(u, v);
        return 1;
    } else {
        apd(u, v), apd(v, u);
        return 0;
    }
}