#include"treasure.h"
const int NN=1e6+5;
int dfn[NN],tot;
vector<int> ed[NN];
void DFS(int x){
if(dfn[x])return;
dfn[x]=++tot;
for(int y:ed[x]){
if(dfn[y])continue;
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]);
}
DFS(x);
for(int i=0;i<m;i++){
if(dfn[u[i]]<dfn[v[i]])dir[i]=1;
else dir[i]=0;
}
return;
}
typedef pair<int,bool> pa;
int Work2(){
int p=0,lst=0;
while(1){
vector<pa> e = discover(p);
int cnt=0;
bool d=0;
long long x=0;
for(pa eg:e){
if(eg.first==lst)continue;
if(eg.first==1)cnt++;
if(d=1)
if(eg.first==0){
d=1;
}
}
}
}
int Bob(const int testid, const int n){
if(testid==4||testid==5||testid==9||testid==10||testid==11||testid==12||testid==13)return Work2();
int p=rd()%n;
while(1){
vector<pa> e = discover(p);
bool d=0;
for(pa eg:e){
if(!eg.second){
d=1;p=eg.first;
break;
}
}
if(!d)break;
}
return p;
}