#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
#include "game.h"
using namespace std;

void fastIO(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
}

int N, M, K;


vector<int> adj[100100];
 
stack<int> S;
 
int cnt = 0;
int dfn[100100], low[100100];
bool in_stack[100100];
int time_in = 0;
int kingdom[100100];

int self_e[100100];

int pre_time_in = 0;
void init(int n, int k){
    N = n;
    K = k;
    for (int i = 0; i < k-1; i++){
        adj[i].push_back(i+1);
    }
}

int kcnt[100100];

void dfs(int node){
    dfn[node] = ++time_in;
    low[node] = dfn[node];
    S.push(node);
    in_stack[node] = true;
    for (int nx : adj[node]){
        if (dfn[nx] <= pre_time_in){
            dfs(nx);
            low[node] = min(low[node], low[nx]);
        } else if (in_stack[nx]){
            low[node] = min(low[node], dfn[nx]);
        }
    }
    if (low[node] == dfn[node]){
        ++cnt;
        while (S.top() != node){
            kcnt[cnt]++;
            kingdom[S.top()] = cnt;
            in_stack[S.top()] = false;
            S.pop();
        }
        kcnt[cnt]++;
        kingdom[S.top()] = cnt;
        in_stack[S.top()] = false;
        S.pop();
    }
}


bool good = false;


int add_teleporter(int u, int v){
    if (good) return true;
    if (u == v){
        self_e[u]++;
    }
    pre_time_in = time_in;
    adj[u].push_back(v);
    cnt = 0;
    for (int i = 0; i < K; i++){
        kingdom[i] = 0;
    }
    while (!S.empty()){
        in_stack[S.top()] = false;
        S.pop();
    }
    /*if (u == 2){
        cout << pre_time_in << "\n";
        for (int i = 0; i < N; i++){
            cout << dfn[i] << " ";
        }
        cout << "\n";
        for (int i = 0; i < N; i++){
            cout << low[i] << " ";
        }
        cout << "\n";
        for (int i = 0; i < N; i++){
            cout << in_stack[i] << " ";
        }
        cout << "\n";
    }*/
    for (int i = 0; i < K; i++){
        if (dfn[i] <= pre_time_in){
            dfs(i);
        }
    }
    /*if (u == 2){
        for (int i = 0; i < N; i++){
            cout << kingdom[i] << " ";
        }
        cout << "\n";
    }*/
    bool work = false;
    for (int i = 0; i < K; i++){
        if (kcnt[kingdom[i]] > 1 || self_e[i]){
            work = true;
            good = true;
        }
    }
    for (int i = 1; i <= cnt; i++) kcnt[i] = 0;
    return work;
}