//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;
int counter = 0;
const int mx = 5e5 + 5; //size limit
vector<int> adj[mx], scc_nodes[mx];
vector<int> comp_graph[mx];
int visited[mx], instack[mx], disc[mx], lowlink[mx], comp[mx];
set<int> comp_nodes;

int comp_visited[mx], comp_instack[mx], comp_disc[mx], comp_lowlink[mx], comp_comp[mx];
bool found = false;

//adj - adjacency list of the graph
//visitied - indicates if a node is visited or not
//instack - indicates if a node is currently in the stack or not
//disc - tells discovery time of that node
//lowlink - tells the lowlink value of that node
//comp - indicates which SCC the node belongs to
//comp_visited - indicates if a component is visited or not for comp tarjan
//comp_instack - indicates if a component is in the stack or not
//comp_disc - tell discovery time of that comp
//comp_lowlink - tells the lowlink value of the comp
//comp_comp - shows if the component has changed it's bigger component
//comp_graph - forest of inter comp edges
//comp_nodes - list of existing components

int yeah = 0, nah = 0; // count of yes and no

void tarjan(int u, stack<int> &st)
{
	disc[u] = lowlink[u] = ++counter;
	st.push(u);
	visited[u] = 1;
	instack[u] = 1;
	
	for(auto v : adj[u])
	{
		if(visited[v] == 0)
		{
			tarjan(v, st);
			lowlink[u] = min(lowlink[u], lowlink[v]);
		}
		else if(instack[v])
			lowlink[u] = min(lowlink[u], disc[v]); //This condition in only specific for articulation points
			// for bridges and SCC we can use lowlink[u]= min(lowlink[u], lowlink[v])
			// But here the definition of lowlink will obviously change
	}
	
	if(disc[u] == lowlink[u])
	{
		int node;
		do{
			node = st.top();
			st.pop();
			//cout<<node<<" ";
			instack[node] = 0;
			comp[node] = u;
		}while(node != u);
		//cout<<"\n";
	}
	
}

//To reset all values to perfrom tarjan again
void reset(int origin)
{
	for(int i : scc_nodes[origin])
	{
		visited[i] = 0;
		instack[i] = 0;
		disc[i] = 0;
		lowlink[i] = 0;
	}
	counter = 0;
}

vector<int> affected_comps; // to store all components that change after edge added b/w 2 different components

void super_join(int u, stack<int> &comp_st, int marker)
{
	comp_disc[u] = comp_lowlink[u] = ++counter;
	comp_st.push(u);
	comp_visited[u] = marker;
	comp_instack[u] = marker;
	comp_comp[u] = u;
	
	
	for(auto v : comp_graph[u])
	{
		if(comp_visited[comp[v]] != marker)
		{
			super_join(comp[v], comp_st, marker);
			comp_lowlink[u] = min(comp_lowlink[u], comp_lowlink[comp[v]]);
		}
		else if(comp_instack[comp[v]] == marker)
			comp_lowlink[u] = min(comp_lowlink[u], comp_disc[comp[v]]); //This condition in only specific for articulation points
			// for bridges and SCC we can use lowlink[u]= min(lowlink[u], lowlink[v])
			// But here the definition of lowlink will obviously change
	}
	
	if(comp_disc[u] == comp_lowlink[u])
	{
		int node;
		do{
			node = comp_st.top();
			comp_st.pop();
			//cout<<node<<" ";
			affected_comps.push_back(node);
			
			comp_instack[node] = 0;
			comp_comp[node] = u;
		}while(node != u);
		//cout<<"\n";
	}
}


int marker = 0;


void insert(int u, int v)
{
	adj[u].push_back(v); // add edge
	
	if(comp[u] == comp[v]) // if edge within component then do nothing
	{
		return;
	}
	else
	{
		comp_graph[comp[u]].push_back(v);

		counter = 0; // reset for new iteration
		
		stack<int> comp_st;
		affected_comps.clear();
		
		marker++;
		
		super_join(comp[u], comp_st, marker);
		
		//reconfiguring all data structures after any possible joins
		
		int origin_comp = comp_comp[comp[u]]; // all merged componenets belong here
		
		vector <int> temp_graph;	
		
		for(int i : affected_comps)
		{	
			if(comp_comp[i] != i && comp_comp[i] == origin_comp)
			{
				for (int vertex : scc_nodes[i])
				{
					comp[vertex] = origin_comp;
                    if(vertex < k) found = true;
					scc_nodes[origin_comp].push_back(vertex);
				}
				scc_nodes[i].clear();
			
			}
		}
		
		
		for (auto j : comp_graph[origin_comp])
		{
			if(origin_comp != comp_comp[comp[j]])
			{
				temp_graph.push_back(j);
			}
		}
		comp_graph[origin_comp].clear();
		
		for (auto j : temp_graph)
		{
			comp_graph[origin_comp].push_back(j);
		}
		temp_graph.clear();
		
		for(int i : affected_comps)
		{
			if(comp_comp[i] == origin_comp && i != origin_comp)
			{
				for (auto j : comp_graph[i])
				{
					if(comp_comp[i] != comp_comp[comp[j]])
					{
						comp_graph[origin_comp].push_back(j);
					}
				}
				comp_graph[i].clear();
				comp_nodes.erase(i);
			}
		}
		
		comp_nodes.insert(origin_comp);
	}
}

//Runs tarjan for only 1 component
void improved_tarjan(int u, int origin, stack<int> &st)
{
	disc[u] = lowlink[u] = ++counter;
	st.push(u);
	visited[u] = 1;
	instack[u] = 1;
	
	for(auto v : adj[u])
	{
		if(comp[v] == origin && visited[v] == 0)
		{
			improved_tarjan(v, origin, st);
			lowlink[u] = min(lowlink[u], lowlink[v]);
		}
		else if(instack[v])
			lowlink[u] = min(lowlink[u], disc[v]); //This condition in only specific for articulation points
			// for bridges and SCC we can use lowlink[u]= min(lowlink[u], lowlink[v])
			// But here the definition of lowlink will obviously change
	}
	
	if(disc[u] == lowlink[u])
	{
		int node;
		do{
			node = st.top();
			st.pop();
			//cout<<node<<" ";
			instack[node] = 0;
			comp[node] = u;
		}while(node != u);
		//cout<<"\n";
	}
	
}

void init(int n_, int k_){
    n = n_, k = k_;
    for(int i = 0; i < k - 1; i++) insert(i, i + 1);
    stack<int> st;
	
	// Run initial Tarjan
	for(int i = 0; i < n; i++)
	{
		if(!visited[i])
			tarjan(i, st);
	}
	
	// Add inter-component edges based on initial results
	for(int i = 0; i < n; i++)
	{
		comp_nodes.insert(comp[i]);
		
		scc_nodes[comp[i]].push_back(i);
		
		for(auto j : adj[i])
		{
			if(comp[j] != comp[i])
			{
				comp_graph[comp[i]].push_back(j);
			}
		}
	}
}

int add_teleporter(int u, int v){
    if(u == v) return u < k;
    insert(u, v);
    return found;
}