#include <bits/stdc++.h>
#include "treasure.h"
using namespace std;
#define eb emplace_back
const int N=2e6+5,B=2e3;
int d[N];bool r[N];queue<int> q;vector<int> e[N];
void Alice(int type,int n,int m,int x,const int u[],const int v[],bool dir[])
{
	assert(n<=5e3);
	for(int i=0;i<m;++i) e[u[i]].eb(v[i]),e[v[i]].eb(u[i]);
	fill(d,d+n,-1);d[x]=0;q.push(x);
	while(!q.empty())
	{
		int u=q.front();q.pop();
		for(auto v:e[u]) if(d[v]==-1) d[v]=d[u]+1,q.push(v);
	}
	for(int i=0;i<m;++i)
		if(d[u[i]]<=B && d[v[i]]<=B) dir[i]=d[u[i]]<d[v[i]];
		else dir[i]=d[u[i]]&1;
	for(int i=0,t;i<n;++i) if(d[i]>B && d[i]&1)
	{
		t=0;for(auto j:e[i]) t+=e[j].size()<2;
		if(t>1) for(auto j:e[i]) if(e[j].size()<2) r[j]=1;
	}
	for(int i=0;i<m;++i) if(r[u[i]] || r[v[i]]) dir[i]^=1;
}
vector<pair<int,bool>> mem[N];mt19937 rand1;
int rdm(int l,int r)
{return uniform_int_distribution<int>(l,r)(rand1);}
auto get(int u)
{
	if(!mem[u].empty()) return mem[u];
	return mem[u]=discover(u);
}
bool chk(int u)
{
	int o=-1,t=0,t1=0;auto e=get(u);
	for(auto [v,dir]:e) if(!dir) o=v,++t;
	if(t>1) return 0;if(t) u=o,e=get(u);
	t=0;for(auto [_,dir]:e) t+=!dir;
	if(t>1) return 0;if(t) return 1;
	for(auto [v,_]:e)
	{
		if(t1>1) break;auto e1=get(v);++t1;
		if(e1.size()>1) {t=0;for(auto [_,dir]:e1) t+=!dir;return t<2;}
	}
	return 1;
}
int find(int u)
{
	auto e=get(u);
	for(auto [v,dir]:e) if(!dir) return v;return -1;
}
int Bob(int testid,int n)
{
	int u;while(1) {u=rdm(0,n-1);if(chk(u)) break;}
	while(1) {int v=find(u);if(v==-1) break;u=v;}return u;
}