#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;

std::unordered_set<int64_t> set;

std::vector<std::pair<int, int>> edg;
static int cnt = 0;

void rebuild_mst(std::unordered_set<int64_t>& set) {
    std::cerr << "REBUILD " << edg.size() << std::endl;

    if (++cnt % 10 == 0) {
        edg.erase(std::remove(edg.begin(), edg.end(), std::pair<int, int>(-1, -1)), edg.end());
        std::shuffle(edg.begin(), edg.end(), rnd);
    }
    static std::vector<int> prv;
    prv.assign(n, -1);
    auto get = [&](auto get, int v) -> int {
        return prv[v] == -1 ? v : prv[v] = get(get, prv[v]);
    };

    set.clear();
    for (auto& [u, v] : edg) {
        if (u == -1 || !gr[u][v]) {
            u = v = -1;
            continue;
        }
        if (get(get, u) != get(get, v)) {
            set.insert(u + int64_t(v) * int(1e9));
            prv[get(get, u)] = v;
            if (set.size() == n - 1) {
                return;
            }
        }
    }
}

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;
    }

    edg.clear();
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            // if (gr[i][j]) {
            edg.push_back({i, j});
            // }
        }
    }
    std::shuffle(edg.begin(), edg.end(), rnd);
    rebuild_mst(set);
}
bool check_conn(int u, int v) {
    // std::cerr << "f";
    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);
    // }
    if (u > v) {
        std::swap(u, v);
    }
    gr[u][v] = gr[v][u] = 0;

    if (!set.count(u + int64_t(v) * int(1e9))) {
        return 0;
    }

    if (check_conn(u, v)) {
        rebuild_mst(set);

        return 0;
    }
    gr[u][v] = gr[v][u] = 1;
    return 1;
}

In file included from /usr/include/c++/13/string:43,
                 from /usr/include/c++/13/bitset:52,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:52,
                 from answer.code:5:
/usr/include/c++/13/bits/allocator.h: In destructor ‘std::__detail::_Hashtable_ebo_helper<0, std::allocator<std::__detail::_Hash_node<long int, false> >, true>::~_Hashtable_ebo_helper()’:
/usr/include/c++/13/bits/allocator.h:184:7: error: inlining failed in call to ‘always_inline’ ‘std::allocator< <template-parameter-1-1> >::~allocator() noexcept [with _Tp = std::__detail::_Hash_node<long int, false>]’: target specific option mismatch
  184 |       ~allocator() _GLIBCXX_NOTHROW { }
      |       ^
In file included from /usr/include/c++/13/bits/hashtable.h:35,
                 from /usr/include/c++/13/bits/unordered_map.h:33,
                 from /usr/include/c++/13/unordered_map:41,
                 from /usr/include/c++/13/functional:63,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:53:
/usr/include/c++/13/bits/hashtable_policy.h:1211:12: note: called from here
 1211 |     struct _Hashtable_ebo_helper<_Nm, _Tp, true>
      |            ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~