#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define vll vector<ll>
int n,k;
const int N=3e4+10;
vector<int> adj[N];
void init(int Q, int P)
{
n=Q;
k=P;
for(int i=0;(i+1)<k;i++)
adj[i].push_back(i+1);
}
bool cycle=0;
vector<int> path;
int vis[N];
bool have[N];
int cur=1;
void dfs(int x,int p=-1)
{
path.push_back(x);
have[x]=1;
vis[x]=cur;
for(auto y:adj[x])
{
if(vis[y]==0) // Never visited in any other dfs
{
dfs(y,x);
if(cycle)
return;
}
else if(vis[y]==cur and have[y]){ // Visited in this dfs but cycle is not guranteed
vll ex={y};
while(path.back()!=y)
{
ex.pb(path.back());
path.pop_back();
}
if(path.size()==0)
{
exit(-10);
}
for(auto lp:ex)
{
if(lp<k)
{
cycle=1;
return;
}
}
while(ex.size())
{
path.pb(ex.back());
ex.pop_back();
}
}
else{// Visited in other dfs but it will not make a cycle
// bcz if it would there would be a path from there to current node but if a path existed then we would have visited this vertex in the same dfs
}
}
path.pop_back();
have[x]=0;
}
int add_teleporter(int u, int v)
{
adj[u].push_back(v);
memset(vis,0,sizeof(vis));
cur=1;
for(int sp=0;sp<k;sp++)
{
if(!vis[sp])
{
path.clear();
cycle=0;
dfs(sp);
if(cycle)
{
return 1;
}
cur++;
}
}
return 0;
}
