//https://qoj.ac/contest/948/problem/4251
//#pragma GCC optimize("O3")
//#pragma GCC optimization ("unroll-loops")
//#pragma GCC target("avx,avx2,fma")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,tune=native")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include "game.h"
using namespace __gnu_pbds;
using namespace std;

#define pb push_back
#define ff first
#define ss second

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pld;

const int INF = 1e9;
const ll LLINF = 1e18;
const int MOD = 1e9 + 7;

template<class K> using sset =  tree<K, null_type, less<K>, rb_tree_tag, tree_order_statistics_node_update>;

inline ll ceil0(ll a, ll b) {
    return a / b + ((a ^ b) > 0 && a % b);
}

const int MX = 300;
int n, k;
int l[300005][2], r[300005][2];
vector<int> g1[300005];
vector<int> g2[300005];

void dfs1(int x){
	if(x < k) return;
	for(int i : g1[x]){
		if(r[x][0] > r[i][0]){
			r[i][0] = r[x][0];
			dfs1(i);
		}
	}
}

void dfs2(int x){
	if(x < k) return;
	for(int i : g2[x]){
		if(l[x][0] < l[i][0]){
			l[i][0] = l[x][0];
			dfs2(i);
		}
	}
}

void init(int n_, int k_){
	n = n_, k = k_;
	for(int i = 0; i < k; i++) l[i][0] = r[i][0] = i/MX, l[i][1] = r[i][1] = i;
	for(int i = k; i < n; i++) l[i][0] = l[i][1] = INF, r[i][0] = r[i][1] = -INF;
}

void dfs3(int x){
	for(int i : g1[x]){
		if(r[x][0] == r[i][0] && r[x][1] > r[i][1]){
			r[i][1] = r[x][1];
			dfs3(i);
		}
	}
}

void dfs4(int x){
	for(int i : g2[x]){
		if(l[x][0] == l[i][0] && l[x][1] < l[i][1]){
			l[i][1] = l[x][1];
			dfs4(i);
		}
	}
}

int add_teleporter(int u, int v){
	if(u < k && v < k && u >= v) return 1;
	if(u == v) return 0;
	g1[u].pb(v);
	g2[v].pb(u);
	bool prv = (l[u][0] > r[u][0] || l[v][0] > r[v][0]);
	r[v][0] = max(r[v][0], r[u][0]);
	l[u][0] = min(l[u][0], l[v][0]);
	r[v][1] = max(r[v][1], r[u][1]);
	l[u][1] = min(l[u][1], l[v][1]);
	dfs1(v);
	dfs2(u);
	if(v > k && r[v][0] > l[v][0]) return 1;
	if(v > k && r[v][1] >= l[v][1]) return 1;
	if(u > k && r[u][0] > l[u][0]) return 1;
	if(u > k && r[u][1] >= l[u][1]) return 1;
	for(int i = l[u][0]*MX; i < min(k, (l[u][0] + 1)*MX); i++){
		dfs3(i);
		dfs4(i);
	}
	if(v > k && r[v][1] >= l[v][1]) return 1;
	if(u > k && r[u][1] >= l[u][1]) return 1;
	return 0;
}