#include "game.h"

#include <bits/stdc++.h>

using namespace std;

const int N = 30010;

vector<int> g1[N], g2[N];
int mn[N], mx[N], used[N], timer = 0;

int n, k;

void init(int this_n, int this_k) {
    n = this_n, k = this_k;
    for (int i = 0; i < n; i++) mn[i] = (int) 1e9, mx[i] = -(int) 1e9;
    for (int i = 0; i < k; i++) mn[i] = i, mx[i] = k - 1;
    for (int i = 0; i < k - 1; i++) g2[i].emplace_back(i + 1);
    for (int i = 0; i < k - 1; i++) g1[i + 1].emplace_back(i);
}

int start;

void update_min(int v, int cur_mn = (int) 1e9) {
    if (used[v] == timer || (v != start && v >= k && cur_mn >= mn[v])) return;
    cur_mn = min(cur_mn, mn[v]);
    used[v] = timer;
    mn[v] = cur_mn;
    for (auto u: g1[v])
        update_min(u, cur_mn);
}

void update_max(int v, int cur_mx = -(int) 1e9) {
    if (used[v] == timer || (v != start && v >= k && cur_mx <= mx[v])) return;
    cur_mx = max(cur_mx, mx[v]);
    used[v] = timer;
    mx[v] = cur_mx;
    for (auto u: g2[v])
        update_max(u, cur_mx);
}

int add_teleporter(int u, int v) {
    if (u == v && u < k) return 1;
    if (mn[v] <= mx[u]) return 1;
    g1[v].emplace_back(u);
    g2[u].emplace_back(v);
    ++timer;
    start = v;
    update_min(v, mn[v]);
    ++timer;
    start = u;
    update_max(u, mx[u]);
    return 0;
}