#include "game.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 3e5+5;
const int MAXB = 20;
vector<int> edges[MAXN];
vector<int> rev[MAXN];
int mxin[MAXN];
int mnout[MAXN];
int n, k;
bool rev_dfs(int cur) {
if (mnout[cur] <= mxin[cur]) return 1;
for (int nxt: rev[cur]) {
if (mnout[cur] < mnout[nxt]) {
mnout[nxt] = mnout[cur];
rev_dfs(nxt);
}
}
return 0;
}
bool dfs(int cur) {
if (mnout[cur] <= mxin[cur]) return 1;
for (int nxt: edges[cur]) {
if (mxin[cur] > mxin[nxt]) {
mxin[nxt] = mxin[cur];
dfs(nxt);
}
}
return 0;
}
bool add_edge(int u, int v) {
edges[u].push_back(v);
rev[v].push_back(u);
if (v < k && mnout[u] > v) {
mnout[u] = v;
if (rev_dfs(u)) return 1;
}
if (mnout[v] < mnout[u]) {
mnout[u] = mnout[v];
if (rev_dfs(u)) return 1;
}
if (mxin[u] > mxin[v]) {
mxin[v] = mxin[u];
if (dfs(v)) return 1;
}
return 0;
}
void init(int N, int K) {
n = N;
k = K;
fill(mxin, mxin+n, -1);
fill(mnout, mnout+n, n);
for (int i = 0; i < k; i++) {
mxin[i] = i; mnout[i] = i+1;
}
}
int add_teleporter(int u, int v) {
return add_edge(u, v);
}
