#pragma GCC target("avx512vl,avx512bw,avx512bitalg,avx512dq")
#pragma GCC optimize("O3")
#include "game.h"

#include <bits/stdc++.h>

constexpr int N = 1501;
// std::vector<std::vector<int>> gr;
std::array<std::bitset<N>, N> gr;
int n;
std::mt19937 rnd;

void initialize(int n) {
    // while (clock() * 1.0 / CLOCKS_PER_SEC < 0.95) {
    //     ;
    // }
    // exit(0);
    ::n = n;
    for (int i = 0; i < n; i++) {
        gr[i].reset();
        gr[i] = ~gr[i];
        gr[i][i] = 0;
    }
}

bool check_conn(int u, int v) {
    static std::bitset<N> used;
    used.reset();
    used = ~used;
    int ans = -1;
    auto dfs = [&](auto dfs, int i) -> void {
        if (i == v) {
            ans = 0;
            return;
        }
        int t = (used & gr[i])._Find_first();
        assert(used[i]);
        used[i] = 0;
        while (t < n) {
            dfs(dfs, t);
            if (ans != -1) {
                return;
            }
            t = (used & gr[i])._Find_next(t);
        }
    };
    dfs(dfs, u);
    if (ans == 0) {
        return true;
    }
    return false;
}

int hasEdge(int u, int v) {
    if (rnd() % 2) {
        std::swap(u, v);
    }
    gr[u][v] = gr[v][u] = 0;

    if (check_conn(u, v)) {
        return 0;
    }
    gr[u][v] = gr[v][u] = 1;
    return 1;
}