#include<bits/stdc++.h>
#include "treasure.h"
using namespace std ;

const int N = 1e6+10 , M = 2e6+10 ;

struct nn
{
    int lst , to , id ;
}E[M<<1] ;
int head[N] , tot = 1 ;
inline void add( int x , int y , int id )
{
    E[++tot] = (nn){head[x],y,id} ;
    head[x] = tot ;
}
int dfn[N] , tim , U[N] , V[N] , id[N] ;
bool D[N] ;
void Assign( int id , int x , int y )
{
    if( U[id]==x ) D[id] = 0 ;
    else D[id] = 1 ;
}//0:原方向
void dfs( int x , int inE )
{
    dfn[x] = ++tim ;
    for(int i = head[x] ; i ; i = E[i].lst ) {
        if( i == (inE^1) ) continue ;
        int t = E[i].to ;
        if( !dfn[t] ) {
            dfs(t,i) ;
            Assign(E[i].id,t,x) ; 
        }
        else {
            if( dfn[t]>dfn[x] ) continue ;
            Assign(E[i].id,x,t) ;
        }
    }
}
void Alice(const int testid, const int n, const int m, const int x, const int u[], const int v[], bool dir[])
{
    srand(time(0)) ;
    for(int i = 0 ; i < m ; i ++ ) {
        id[i] = i ;
        U[i] = u[i] , V[i] = v[i] ;
    }
    random_shuffle(id,id+m) ;
    for(int i = 0 ; i < m ; i ++ ) {
        int ID = id[i] ;
        add(u[ID],v[ID],ID) ; add(v[ID],u[ID],ID) ;
    }
    dfs(x,0) ;
    for(int i = 0 ; i < m ; i ++ ) dir[i] = D[i] ;
}

vector<pair<int,bool>> discover(int pos) ;
vector<pair<int,bool>> ee ;
int tmp[N] , len ;
bool vis[N] ;
mt19937 rnd(time(0)) ;
int Bob(const int testid, const int n)
{
    int B = sqrt(n) ;
    while( 1 ) {
        int x = rnd()%n ;
        if( vis[x] ) continue ;
        vis[x] = 1 ;
        for(int i = 1 , now = x ; i <= B ; i ++ ) {
            ee = discover(now) ; len = 0 ;
            for(int i = 0 ; i < ee.size() ; i ++ ) {
                if( ee[i].second == 0 ) tmp[++len] = ee[i].first ;
            }
            if( len == 0 ) { // 到达终点
                return now ;
            }
            int p = rnd()%len+1 ;
            now = tmp[p] ;
        }
    }
}