// Skyqwq
#include <bits/stdc++.h>

#define pb push_back
#define fi first
#define se second
#define mp make_pair

using namespace std;

typedef pair<int, int> PII;
typedef long long LL;

template <typename T> bool chkMax(T &x, T y) { return (y > x) ? x = y, 1 : 0; }
template <typename T> bool chkMin(T &x, T y) { return (y < x) ? x = y, 1 : 0; }

#include "game.h"

const int N = 3e5 + 5, L = 21;
int c[L][N], K, cr[N << 3];
bool vg[L][N], vh[L][N], ok;
vector<int> g[N], h[N];

#define ls (p << 1)
#define rs (p << 1 | 1)

void cz(int u, int p, int d);

void dfs1(int u, int id, int d) {
  //cout << u << " dfs" << id << " " << d << endl;
  vg[d][u] = 1;
  if (u != cr[id] && vh[d][u]) ok = 1;
  if (!c[d][u]) {
    c[d][u] = id;
    cz(u, id, d);
  }
  if (cr[id << 1 | 1] && !c[d + 1][u]) {
    c[d + 1][u] = id << 1 | 1;
    cz(u, id << 1 | 1, d + 1);
  }
  for (int v: g[u]) {
    if (v == cr[id]) ok = 1;
    if ((c[d][v] == id || !c[d][v]) && !vg[d][v]) {
      dfs1(v, id, d);
    }
  }
}


void dfs2(int u, int id, int d) {
  vh[d][u] = 1;
  if (u != cr[id] && vg[d][u]) ok = 1;
  if (!c[d][u]) {
    c[d][u] = id;
    cz(u, id, d);
  }
  if (cr[id << 1] && !c[d + 1][u]) {
    c[d + 1][u] = id << 1;
    cz(u, id << 1, d + 1);
  }
  for (int v: h[u]) {
    if (v == cr[id]) ok = 1;
    if ((c[d][v] == id || !c[d][v]) && !vh[d][v]) {
      dfs2(v, id, d);
    }
  }
}

void cz(int u, int p, int d) {
  if (!vg[d][u])for (int v: h[u]) {
    if (c[d][v] == p && vg[d][v])
      dfs1(u, p, d);
  }
  if (!vh[d][u]) for (int v: g[u]) {
    if (c[d][v] == p && vh[d][v])
      dfs2(u, p, d);
  }
}

void bd(int p, int l, int r, int d) {
  if (l > r) return;
  int mid = (l + r) >> 1;
  cr[p] = mid;
  for (int i = l; i <= r; i++)
    c[d][i] = p;
  for (int i = d + 1; i < L; i++) c[i][mid] = -1;
  bd(ls, l, mid - 1, d + 1);
  bd(rs, mid + 1, r, d + 1);
}

void bd2(int p, int l, int r, int d) {
  if (l > r) return;
  int mid = (l + r) >> 1;
  dfs1(mid, p, d);
  dfs2(mid, p, d);
  for (int i = d + 1; i < L; i++) c[i][mid] = -1;
  bd2(ls, l, mid - 1, d + 1);
  bd2(rs, mid + 1, r, d + 1);
}

void init(int n, int k) { 
   K = k;
   for (int i = 1; i < K; i++) g[i].pb(i + 1), h[i + 1].pb(i);
   bd(1, 1, K, 0);
  bd2(1, 1, K, 0);
}


void wk1(int p, int l, int r, int d, int u, int v) {
  if (l > r || ok) return;
  int mid = (l + r) >> 1;
  // cout << p << " " << l << "?" << r << " dd " << d << "?" << u << " " << v << endl;
  // cout << vg[d][u] << "?" << vg[d][v] << " haha " << c[d][v] << endl;
  if (vg[d][u] && !vg[d][v] && (c[d][v] == p || !c[d][v])) {
    dfs1(v, p, d);
    if (ok) return;
    
  }
 //  cout << vh[d][v] << "?" << vh[d][u] << " " << c[d][u] << " haha " << endl;
  if (vh[d][v] && !vh[d][u] && (c[d][u] == p || !c[d][u])) {
    dfs2(u, p, d);
    if (ok) return;
    
  }
  if (mid == u || mid == v) return;
 // cout << c[d + 1][u] << "??" << c[d + 1][v] << " why\n";
  if (c[d + 1][u] == ls && (c[d + 1][v] == ls)) {
    wk1(ls, l, mid - 1, d + 1, u, v);
  } else if (c[d + 1][u] == rs && (c[d + 1][v] == rs)){
    wk1(rs, mid + 1, r, d + 1, u, v);
  }
}


 int dfn[N], low[N], pre[N];
  int s[N], top, dfncnt;
  bool ins[N];

void inline clr() {
  for (int i = 1; i <= dfncnt; i++) {
    int u = pre[i];
    dfn[u] = low[u] = ins[u] = 0;
  }
  top = dfncnt = 0;
}

bool tarjan(int u) {
  dfn[u] = low[u] = ++dfncnt;
  s[++top] = u, ins[u] = 1;
  for (int v: g[u]) {
    if (!dfn[v]) {
      if (tarjan(v)) return 1;
       chkMin(low[u], low[v]);
    }
    else if (ins[v]) chkMin(low[u], dfn[v]);
  }
  if (dfn[u] == low[u]) {
    int v;
    int sz = 0;
    bool ok = 0;
    do {
      sz++;
      v = s[top--];
      ins[v] = 0;
      if (v <= K) ok = 1;
      if (ok && sz > 1) return 1;
    } while (v != u);
  }
  return 0;
}

int now = 0;

int add_teleporter(int u, int v) {
  u++, v++;
//  cout << " fuck for " << vg[1][6] << endl;
  if (u == v && u <= K) ok = 1;
  if (ok) return 1;
  g[u].pb(v); h[v].pb(u);
  wk1(1, 1, K, 0, u, v);
  if(++now==50000){
    ok |= tarjan(1);
    clr();
  }
  return ok;
}