#include"treasure.h"
#include<bits/stdc++.h>
const int NN=1e6+5;
int dep[NN];
vector<int> ed[NN];
void DFS(int x){
	for(int y:ed[x]){
		if(dep[y])continue;
		dep[y]=dep[x]+1;
		DFS(y);
	}
	return;
}
void Alice(const int testid, const int n, const int m, const int x, const int u[], const int v[], bool dir[]){
    for(int i=0;i<m;i++){
    	ed[u[i]].push_back(v[i]);
    	ed[v[i]].push_back(u[i]);
	}
	dep[x]=1;DFS(x);
	for(int i=0;i<m;i++){
		if(max(dep[v[i]],dep[u[i]])<=max(100,(int)sqrt(n))){
			if(dep[u[i]]<dep[v[i]])dir[i]=1;
			else dir[i]=0;
		}else{
			if(max(dep[v[i]],dep[u[i]])&1)dir[i]=1;
			else dir[i]=0;
		}
	}
	return;
}
typedef pair<int,bool> pa;
bool vst[NN];
unordered_map<int,vector<pa> > mp;
int Bob(const int testid, const int n){
	mt19937 rnd(time(0));
	int p=rnd()%n;
	while(1){
		p=rnd()%n;
		if(mp.find(p)==mp.end()){
			mp[p]=discover(p);
		}
		int in=0,out=0;
		for(pa eg:mp[p])eg.second?in++:out++;
		if(in&&out)break;
	}
	while(1){
		if(mp.find(p)==mp.end())mp[p] = discover(p);
    	bool d=0;
	    for(pa eg:mp[p])
	    	if(!eg.second){p=eg.first;d=1;break;}
	    if(!d)break;
	}
	mark:;
	return p;
}