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

#include <bits/stdc++.h>

constexpr int N = 512 * 3;
// 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 % 500 == 0) {
        edg.erase(std::remove(edg.begin(), edg.end(), std::pair<int, int>(-1, -1)), edg.end());
        // std::cerr << "SHF\n";
        std::shuffle(edg.begin(), edg.begin() + std::min<int>(edg.size(), 2e3), rnd);
    }

    static std::vector<int> prv, sz;

    prv.assign(n, -1);
    sz.assign(n, 1);
    auto get = [&](auto get, int v) -> int {
        return prv[v] == -1 ? v : prv[v] = get(get, prv[v]);
    };
    auto unite = [&](int u, int v) {
        u = get(get, u);
        v = get(get, v);
        assert(u != v);
        if (sz[u] < sz[v]) {
            std::swap(u, v);
        }
        sz[u] += sz[v];
        prv[v] = u;
    };

    set.clear();
    int iter = 0;
    for (int i = 0; i < edg.size(); i++) {
        auto& [u, v] = edg[i];

        if (u == -1 || !gr[u][v]) {
            u = v = -1;
            continue;
        }
        iter++;
        if (get(get, u) != get(get, v)) {
            unite(u, v);
            set.insert(u + int64_t(v) * int(1e9));
            std::swap(edg[set.size() - 1], edg[i]);
            if (set.size() == n - 1) {
                // std::cerr << i << " " << i - iter << "\n";
                if (i - iter > 1e3) {
                    edg.erase(std::remove(edg.begin(), edg.end(), std::pair<int, int>(-1, -1)), edg.end());
                    // std::cerr << "RM\n";
                }
                // std::partition(edg.begin(), edg.beg)
                // if (iter > 1.5e4) {
                //     cnt = 0;
                //     std::cerr << "SHF\n";
                //     std::shuffle(edg.begin(), edg.end(), rnd);
                // }
                return;
            }
        }
    }
    assert(false);
}

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";
    if ((gr[u] & gr[v])._Find_first() < n) {
        return true;
    }
    static std::bitset<N> used;
    used.reset();
    used = ~used;
    int ans = -1;
    auto dfs = [&](auto dfs, int i) -> void {
        if (i == v || gr[v][i]) {
            ans = 0;
            return;
        }
        auto bt = used & gr[i];
        int t = bt._Find_first();
        assert(used[i]);
        used[i] = 0;
        while (t < n) {
            dfs(dfs, t);
            if (ans != -1) {
                return;
            }
            bt &= used;
            t = bt._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 (rnd() % 2) {
        std::swap(u, v);
    }
    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:6:
/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>
      |            ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~