#include <bits/stdc++.h>
#include "game.h"
using namespace std;

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

int N, K;

bool good = false;
int earl[21][300100], late[21][300100];
vector<int> g[300100], rev[300100];

void build(int node, int l, int r, int h){
    for (int i = l; i <= r; i++){
        earl[h][i] = late[h][i] = node;
    }
    if (l == r){
        return;
    }
    int mid = (l+r)/2;
    build(node*2, l, mid, h+1);
    build(node*2+1, mid+1, r, h+1);
}

void init(int n, int k){
    N = n, K = k;
    build(1, 1, K, 1);
}

void dfs(int node, int val, int h){
    if (late[h][node] == 0 || late[h][node] < val){
        late[h][node] = val;
    } else {
        return;
    }
    for (int nx : g[node]){
        dfs(nx, val, h);
    }
}

void dfs2(int node, int val, int h){
    if (earl[h][node] == 0 || earl[h][node] > val){
        earl[h][node] = val;
    } else {
        return;
    }
    for (int nx : rev[node]){
        dfs2(nx, val, h);
    }
}

void dnq(int node, int l, int r, int u, int v, int h){
    if (l == r){
        if (late[h][u]){
            dfs(v, late[h][u], h);
        }
        if (earl[h][v]){
            dfs2(u, earl[h][v], h);
        }
        if (u > K && earl[h][u] == late[h][u] && earl[h][u]) good = true;
        if (v > K && earl[h][v] == late[h][v] && earl[h][v]) good = true;
        return;
    }
    int mid = (l+r)/2;
    if (late[h+1][u]){
        dfs(v, late[h+1][u], h+1);
    }
    if (earl[h+1][v]){
        dfs2(u, earl[h+1][v], h+1);
    }

    //cout << u << " " << v << " " << h << " " << earl[h+1][u] << " " << earl[h+1][v] << "\n";
    if (u > K && earl[h+1][u] && late[h+1][u] && earl[h+1][u] <= late[h+1][u]){
        good = true;
    }
    if (v > K && earl[h+1][v] && late[h+1][v] && earl[h+1][v] <= late[h+1][v]){
        good = true;
    }
    if ((earl[h+1][u] == node*2 && earl[h+1][u] == earl[h+1][v]) || (late[h+1][u] == node*2 && late[h+1][u] == late[h+1][v])){
        dnq(node*2, l, mid, u, v, h+1);
    }
    if ((earl[h+1][u] == node*2+1 && earl[h+1][u] == earl[h+1][v]) || (late[h+1][u] == node*2+1 && late[h+1][u] == late[h+1][v])){
        dnq(node*2+1, mid+1, r, u, v, h+1);
    }
}

int add_teleporter(int u, int v){
    u++, v++;
    if (good) return 1;
    if (u <= K && v <= K && u >= v){
        good = true;
        return 1;
    }
    g[u].push_back(v);
    rev[v].push_back(u);
    dnq(1, 1, K, u, v, 1);
    if (good) return 1;
    return 0;
}