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

const int N = 2e6+10 , M = 2e6+10 ;
// 随机选点后需要快速check是否在 sqrt n 邻域内
// 结合二分图的性质，使得入度或者出度为 0 即可！

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] , dep[N] , Max ;
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] ) {
            dep[t] = dep[x]+1 ;
            dfs(t,i) ;
            Assign(E[i].id,t,x) ; 
        }
        else {
            if( dfn[t]>dfn[x] ) continue ;
            Assign(E[i].id,x,t) ;
        }
    }
}

int c[N] , B ;
void dfs1( int x ) // 黑白染色
{
    for(int i = head[x] ; i ; i = E[i].lst ) {
        int t = E[i].to ;
        if( !c[t] && dep[t]>B ) {
            c[t] = 3-c[x] ;
            dfs1(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)) ;
    // cout << "OK" << endl ;
    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) ;
    }
    dep[x] = 1 ;
    dfs(x,0) ;
    B = sqrt(n) ;
    for(int i = 1 ; i <= n ; i ++ ) {
        if( !c[i] && dep[i] > B+5 ) {
            c[i] = 1 ;
            dfs1(i) ;
        }
    }
    for(int i = 1 ; i <= n ; i ++ ) {
        if( c[i] == 1 ) {
            for(int j = head[i] ; j ; j = E[j].lst ) {
                int t = E[j].to ;
                Assign(E[j].id,i,t) ;
            }
        }
        else if( c[i] == 2 ) {
            for(int j = head[i] ; j ; j = E[j].lst ) {
                int t = E[j].to ;
                Assign(E[j].id,t,i) ;
            }
        }
    }
    for(int i = 0 ; i < m ; i ++ ) dir[i] = D[i] ;
    // cout << "OK" << endl ;
}

vector<pair<int,bool>> discover(int pos) ;
vector<pair<int,bool>> ee[N] , tp ;
int tmp[N] , len ;
bool vis[N] , is[N] ;
mt19937 rnd(time(0)) ;
int Bob(const int testid, const int n)
{
    int B = sqrt(n) ;
    for(int t = 1 ; t <= B+100 ; t ++ ) {
        int x = rnd()%n ;
        if( vis[x] ) continue ;
        vis[x] = 1 ;
        ee[x] = discover(x) ;
        int f0 = 0 , f1 = 0 ;
        for(auto R : ee[x] ) {
            if( R.second ) f1 = 1 ;
            else f0 = 1 ;
        }
        if( (f0&&f1)||(t>=B+60&&f0) ) {
            int now = x ;
            while( 1 ) {
                // printf("%d\n" , now ) ;
                if( !vis[now] ) {
                    vis[now] = 1 ;
                    ee[now] = discover(now) ;
                }
                bool nxt = 0 ;
                for(auto R : ee[now] ) {
                    if( !R.second ) {
                        now = R.first ; nxt = 1 ;
                        break ;
                    }
                }
                if( !nxt ) return now ;
            }
        }
    }
}
/*
1 10 9 0
0 1
0 2
0 3
0 4
0 5
0 6
0 7
0 8
0 9
*/