#include "game.h"
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> G, R;
int N, K;
vector<int> post;
vector<vector<int>> scc;
void dfs(int u, vector<bool> &vis){
vis[u] = 1;
for(int &v : G[u]){
if(!vis[v]) dfs(v, vis);
}
post.push_back(u);
}
void rdfs(int u, vector<bool> &vis, int t){
vis[u] = 1;
scc[t].push_back(u);
for(int v : R[u]){
if(!vis[v]){
rdfs(v, vis, t);
}
}
}
void init(int n, int k) {
N = n, K = k;
G.resize(n);
R.resize(n);
scc.resize(n);
for(int i = 0; i < k - 1; i++){
G[i].push_back(i + 1);
R[i + 1].push_back(i);
}
}
int add_teleporter(int u, int v) {
int tin = 0;
if(u == v) return 0;
post.clear();
for(int i = 0; i < N; i++) scc[i].clear();
G[u].push_back(v);
R[v].push_back(u);
vector<bool> vis(N, 0);
for(int i = 0; i < N; i++){
if(!vis[i]) dfs(i, vis);
}
vis.assign(N, 0);
reverse(post.begin(), post.end());
for(int i : post){
if(!vis[i]){
rdfs(i, vis, tin);
tin++;
}
}
for(int i = 0; i < tin; i++){
int cnt = 0;
for(int j : scc[i]){
if(j < K){
cnt++;
}
}
if(cnt >= 2){
return 1;
}
}
return 0;
}
