// ~~ icebear ~~
#include <bits/stdc++.h>
using namespace std;
int N, K;
vector<int> L, R; // bucket
vector<int> S, T; // max reachable - min be reached
vector<vector<int>> G, rG;
bool update(int U) {
if (U < K) return false;
while(true) {
int M = (L[U] + R[U]) >> 1;
if (S[U] > M || T[U] <= M) {
if (S[U] > M) L[U] = M + 1;
else R[U] = M;
if (L[U] >= R[U]) return true;
for(int V : G[U]) if (S[V] < L[U]) {
S[V] = L[U];
if (update(V)) return true;
}
for(int V : rG[U]) if (T[V] > R[U]) {
T[V] = R[U];
if (update(V)) return true;
}
} else break;
}
return false;
}
void init(int _N, int _K) {
N = _N, K = _K;
L.assign(N, 0);
R.assign(N, N);
S.assign(N, 0);
T.assign(N, N);
G.resize(N);
rG.resize(N);
for(int i = 0; i < K; i++) L[i] = R[i] = S[i] = T[i] = i + 1;
}
int add_teleporter(int U, int V) {
if (U == V) return V < K;
if (U < K && V < K) return U > V;
if (V >= K && S[V] < L[U]) {
S[V] = L[U];
if (update(V)) return true;
}
if (U >= K && T[U] > R[V]) {
T[U] = R[V];
if (update(U)) return true;
}
return false;
}
