#include <bits/stdc++.h>
#include "treasure.h"
void Alice(const int testid,const int n,const int m,const int x,const int u[],const int v[],bool dir[]){
    vector<pair<int,int> > e[n+5];
    for(int i=0;i<m;i++)e[u[i]].push_back({v[i],i+1}),e[v[i]].push_back({u[i],-i-1}),dir[i]=0;
    if(n<=100000){
        queue<int> q;
        vector<int> st,dist;
        for(int i=0;i<n;i++)st.push_back(0),dist.push_back(0);
        q.push(x);
        st[x]=dist[x]=1;
        while(q.size()){
            int t=q.front();q.pop();
            for(pair<int,int> j:e[t])if(!st[j.first])dist[j.first]=dist[t]+1,st[j.first]=1,q.push(j.first);
        }
        for(int i=0;i<m;i++){
            if(dist[u[i]]!=dist[v[i]])dir[i]=(dist[u[i]]<dist[v[i]]);
            else dir[i]=(u[i]<v[i]);
        }
    }
    else{
        vector<int> pnt,st;
        for(int i=0;i<n;i++)st.push_back(0);
        for(int i=0;i<n;i++)if(e[i].size()<=5&&!st[i]){
            pnt.push_back(i);
            for(pair<int,int> j:e[i])st[j.first]=1;
        }
        for(int i=0;i<20;i++){
            if(x>>i&1){
                if(e[pnt[i]][0].second>0)dir[e[pnt[i]][0].second-1]=1;
                else dir[-e[pnt[i]][0].second-1]=0;
            }
            else{
                if(e[pnt[i]][0].second>0)dir[e[pnt[i]][0].second-1]=0;
                else dir[-e[pnt[i]][0].second-1]=1;
            }
            for(int ii=1;ii<e[pnt[i]].size();ii++){
                if(e[pnt[i]][ii].second>0)dir[e[pnt[i]][ii].second-1]=0;
                else dir[-e[pnt[i]][ii].second-1]=1;
            }
        }
    }
}
int Bob(const int testid,const int n){
    if(n<=100000){
        int cur=1;
        while(1){
            vector<pair<int,bool> > ttt=discover(cur);
            int id=n+5;
            for(pair<int,bool> j:ttt)if(!j.second){
                id=j.first;
                break;
            }
            if(id==n+5)return cur;
            cur=id;
        }
    }
    else{
        vector<int> pnt,st;
        for(int i=0;i<n;i++)st.push_back(0);
        int res=0;
        for(int i=0;i<n;i++){
            vector<pair<int,bool> > ttt=discover(i);
            if(ttt.size()<=5&&!st[i]){
                pnt.push_back(i);
                int sum=0;
                for(pair<int,bool> j:ttt)st[j.first]=1,sum+=j.second;
                res+=(sum<<(pnt.size()-1));
                if(pnt.size()==20)return res;
            }
        }
    }
}