#include <bits/stdc++.h>
#define f first
#define s second
#define ent '\n'
//#define int long long
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("Ofast,unroll-loops,fast-math,O3")
const int dx[]={-1, 1, 0, 0, 0};
const int dy[]={0, 0, 1, -1, 0};
typedef long long ll;
using namespace std;
const int mx=1e6+12;
const int mod=998244353;
const bool T=1;
vector<int> g[mx];
vector<int> e[mx];
vector<int> ord;
bool used[mx];
int comp[mx];
int cnt[mx];
int n,m,k;
int timer;
bool ans;
void init(int N, int K) {
n=N, k=K;
timer++;
for(int i=0;i<k-1;i++){
g[i].push_back(i+1);
e[i+1].push_back(i);
}
}
void dfs(int v){
used[v]=1;
for(int to:g[v]){
if(!used[to]){
dfs(to);
}
}
ord.push_back(v);
}
void dfs(int v,int c){
used[v]=1;
cnt[c]++;
comp[v]=c;
for(int to:e[v]){
if(!used[to]){
dfs(to, c);
}
}
}
int add_teleporter(int u, int v) {
if(ans){
return 1;
}
if(v==u && v<k){
ans=1;
return 1;
}
g[u].push_back(v);
e[v].push_back(u);
ord.clear();
for(int i=0;i<=n;i++){
used[i]=cnt[i]=0;
}
for(int i=0;i<n;i++){
if(!used[i]){
dfs(i);
}
}
for(int i=0;i<n;i++){
used[i]=0;
}
int N=0;
reverse(ord.begin(), ord.end());
for(int v:ord){
if(!used[v]){
dfs(v, ++N);
}
}
for(int i=0;i<k;i++){
if(cnt[comp[i]]>1){
ans=1;
return 1;
}
}
return 0;
}
