#include "game.h"
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
int N, K;
vector<vector<int>> adj_list;
vector<vector<int>> revlist;
vector<int> priority;
vector<bool> visited;
vector<int> cnt;
vector<int> idx;
void dfs1(int node) {
if (visited[node]) {
return;
}
visited[node] = true;
for (auto neigh : adj_list[node]) {
dfs1(neigh);
}
priority.pb(node);
}
void dfs2(int node) {
if (visited[node]) {
return;
}
visited[node] = true;
if (idx[node] == -1) {
idx[node] = cnt.size();
cnt.pb(0);
}
cnt[idx[node]]++;
for (auto neigh : adj_list[node]) {
idx[neigh] = idx[node];
dfs2(neigh);
}
}
void components(void) {
visited.assign(N, false);
priority.clear();
for (int i = 0; i < N; i++) {
dfs1(i);
}
idx.assign(N, -1);
visited.assign(N, false);
cnt.clear();
while (!priority.empty()) {
dfs2(priority.back());
priority.pop_back();
}
}
void init(int n, int k) {
N = n;
K = k;
adj_list.resize(N);
revlist.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) {
adj_list[u].pb(v);
revlist[v].pb(u);
components();
for (int i = 0; i < K; i++) {
if (cnt[idx[i]] > 1) {
return 0;
}
}
return 1;
}
