#include "game.h"
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
const int BUCKET = 330;
int N, K;
vector<vector<int>> tmp;
vector<vector<int>> revtmp;
vector<vector<int>> adj_list;
vector<vector<int>> revlist;
//in[node]: Maximum i s.t there is inedge or path to node from i
vector<int> in;
// out[node]: Minimum i s.t there is outedge or path from node to i
vector<int> out;
void dfs(int node, int k, vector<vector<int>>& adj_list, vector<int>& c) {
if (c[node] != -1) {
return;
}
c[node] = k;
for (auto neigh : adj_list[node]) {
dfs(neigh, k, adj_list, c);
}
}
void components(void) {
for (int u = 0; u < N; u++) {
for (auto v : tmp[u]) {
adj_list[u].pb(v);
}
for (auto v : revtmp[u]) {
adj_list[v].pb(u);
}
}
in.assign(N, -1);
out.assign(N, -1);
for (int i = K - 1; i >= 0; i--) {
for (auto u : adj_list[i]) {
dfs(u, i, adj_list, in);
}
}
for (int i = 0; i < K; i++) {
for (auto v : revlist[i]) {
dfs(v, i, revlist, out);
}
}
}
void init(int n, int k) {
N = n;
K = k;
adj_list.resize(N);
revlist.resize(N);
tmp.resize(N);
revtmp.resize(N);
for (int i = 0; i < K - 1; i++) {
adj_list[i].pb(i + 1);
revlist[i + 1].pb(i);
}
}
int add_teleporter(int u, int v) {
if (u == v) {
if (u < K) {
return 1;
}
else {
return 0;
}
}
adj_list[u].pb(v);
revlist[v].pb(u);
components();
for (int i = 0; i < K; i++) {
if (in[i] != -1 && out[i] != -1 && out[i] <= in[i]) {
return 1;
}
}
return 0;
}
