//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);
}

int n, k;
//lowest it can get to, highest it can come from
int l[300005], r[300005];
vector<int> g1[300005];
vector<int> g2[300005];

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

bool found = false;

void dfs(int x){
	if(found) return;
	for(int i : g1[x]){
		if(r[x] >= l[i]){
			found = true;
			return;
		}
		if(l[x] == l[i] && r[x] == r[i]) continue;
		int mid = (r[i] + l[i])/2;
		if(r[x] >= mid){
			r[i] = mid;	
		}
		mid = (r[x] + l[x])/2;
		if(mid >= l[i]){
			l[x] = mid;
		}
		if(r[x] >= r[i]) dfs(i);
	}
	for(int i : g2[x]){
		if(r[i] >= l[x]){
			found = true;
			return;
		}
		if(l[x] == l[i] && r[x] == r[i]) continue;
		int mid = (r[i] + l[i])/2;
		if(l[x] <= mid){
			l[i] = mid;	
		}
		mid = (r[x] + l[x])/2;
		if(mid <= r[i]){
			r[x] = mid;
		}
		if(l[i] >= l[x]) dfs(i);
	}
	if(r[x] >= l[x]){
		found = true;
		return;
	}
}

int add_teleporter(int u, int v){
	g1[u].pb(v);
	g2[v].pb(u);
	dfs(u);
	dfs(v);
	return found;
}