#include "game.h"
#include <bits/stdc++.h>

using namespace std;

#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define pb push_back

struct dsu {
    int n, k;
    vector<int> par, siz, sum;
    dsu() = default;
    dsu(int n_, int k_) {
        n = n_;
        k = k_;
        sum.assign(n, 0);
        for (int i = 0; i < k; i++) sum[i] = 1;
        par.assign(n, 0);
        siz.assign(n, 1);
        iota(all(par), 0);
    }
    int get(int v) {return (par[v] == v ? v : par[v] = get(par[v]));}
    bool merge(int u, int v) {
        u = get(u); v = get(v);
        if (u == v) return false;
        if (siz[u] < siz[v]) swap(u, v);
        par[v] = u;
        sum[u] += sum[v];
        siz[u] += siz[v];
        return (sum[u] >= 2);
    }
};

struct dynamic_scc {
    const int MAXLVL = 19;
    int n, k, step;
    vector<vector<pair<int, int>>> edg_arrs;
    vector<vector<int>> g, grev;
    vector<int> used_dfs, used;
    vector<dsu> dp_dsu;

    dynamic_scc() = default;
    void init(int n_, int k_) {
        step = 0;
        n = n_;
        k = k_;
        used_dfs.assign(n, 0); used.assign(n, 0);
        g.resize(n);
        edg_arrs.resize(MAXLVL);
        dp_dsu.resize(MAXLVL, dsu(n, k));
    }

    bool add_edge(pair<int, int> new_edge) {
        if (new_edge.first == new_edge.second) return new_edge.first < k;
        step++;
        int fb = 0;
        while (!edg_arrs[fb].empty()) fb++;
        for (int j = 0; j < fb; j++) {
            for (auto edg : edg_arrs[j]) {
                edg_arrs[fb].push_back(edg);
            }
            edg_arrs[j].clear();
        }
        edg_arrs[fb].pb(new_edge);

        vector<int> iverts(2 * sz(edg_arrs[fb]));
        for (int i = 0; i < sz(edg_arrs[fb]); i++) {
            int u = edg_arrs[fb][i].first, v = edg_arrs[fb][i].second;
            int cu = dp_dsu[fb].get(u), cv = dp_dsu[fb].get(v);
            if (cu == cv) continue;
            if (used[cu] != step) {
                g[cu].clear(); grev[cu].clear();
                used[cu] = step;
            }
            if (used[cv] != step) {
                g[cv].clear(); grev[cv].clear();
                used[cv] = step;
            }
            g[cu].push_back(cv);
            grev[cv].push_back(cu);
            iverts[2 * i] = cu; iverts[2 * i + 1] = cv;
        }

        vector<int> order;
        auto dfs = [&](int v, auto&&self) -> void {
            used_dfs[v] = step;
            for (int u : g[v]) {
                if (used_dfs[u] != step) {
                    self(u, self);
                }
            }
            order.push_back(v);
        };
        for (int vt : iverts) {
            if (used_dfs[vt] != step) {
                dfs(vt, dfs);
            }
        }

        step++;
        vector<pair<int, int>> dsu_adds;
        auto dfs2 = [&](int v, auto&&self) -> void {
            used_dfs[v] = step;
            for (int u : grev[v]) {
                if (used_dfs[u] != step) {
                    dsu_adds.emplace_back(v, u);
                    self(u, self);
                }
            }
        };
        for (int ind = sz(order) - 1; ind >= 0; ind--) {
            if (used_dfs[order[ind]] != step) {
                dfs2(order[ind], dfs2);
            }
        }
        bool nice = false;
        for (int j = 0; j <= fb; j++) {
            for (auto edg : dsu_adds) {
                nice |= dp_dsu[j].merge(edg.first, edg.second);
            }
        }
        return nice;
    }
};

dynamic_scc dscc;

void init(int n, int k) {
    dscc.init(n, k);
}

int add_teleporter(int u, int v) {
    return dscc.add_edge({u, v});
}