#include "treasure.h"
#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10;
const int B=3003;



namespace NAMESPACE_ALICE{
	int n,m,at;
	vector<array<int,2>> g[N];
	int col[N];
	bool* dir;
	int dis[N];
	void get_near(){
		memset(dis,0x3f,sizeof(dis));
		queue<int> q;
		dis[at]=0;
		q.push(at);
		col[at]=1;
		while(!q.empty()) {
			int u=q.front(); q.pop();
			// fprintf(stderr,"dis %d = %d\n",u,dis[u]);
			for(auto [v,w]:g[u]) if(dis[u]+1<dis[v]){
				dis[v]=dis[u]+1;
				col[v]=col[u]^3;
				q.push(v);
			}
		}
		for(int i=0;i<n;i++) if(dis[i]>B) dis[i]=1e9;;
	}
	void build(){
		for(int u=0;u<n;u++){
			for(auto[v,w]:g[u]) if(w!=-1){
				if(dis[u]!=dis[v]) dir[w]=(dis[u]<dis[v]);
				else dir[w]=(col[u]<col[v]);
				// fprintf(stderr,"link %d %d %d\n",u,v,dir[w]);
			}
		}
	}
	void solve(int _n,int _m,int _x,const int* from,const int* to,bool* _dir){
		n=_n; m=_m; at=_x; dir=_dir;
		for(int i=0;i<m;i++){
			g[from[i]].push_back({to[i],i});
			g[to[i]].push_back({from[i],-1});
		}
		get_near();
		build();
	}
};



namespace NAMESPACE_BOB{
	mt19937 e(20090827);
	int n;
	bool vis[N];
	int solve(int _n){
		n=_n;
		int u=e()%n;
		bool start=true;
		while(true){
			#define check(x,y) {u=x;start=y;continue;}
			if(vis[u]){
				check(e()%n,true);
				continue;
			}
			vector<pair<int,bool>> g=discover(u);
			vis[u]=true;
			if(g.size()==n-1){
				for(auto [v,w]:g) if(!w) {
					return v;
				}
				return u;
			}
			if(g.size()==1){
				if(!start) return u;
				int v=g[0].first;
				if(vis[v]) {
					check(v,true);
				} else check(v,true);
			}
			bool same=true;
			for(int i=1;i<g.size();i++) if(g[i].second!=g[0].second) same=false;
			if(same) {
				if(!start&&g[0].second) return u;
				int v; do v=e()%n; while(vis[v]);
				check(e()%n,true);
			}
			for(auto [v,w]:g) if(!w&&!vis[v]) check(v,false);

		}
	}
};



void Alice(const int testid, const int n, const int m, const int x, const int u[], const int v[], bool dir[]){
	NAMESPACE_ALICE::solve(n,m,x,u,v,dir);
}
int Bob(const int testid, const int n){
	return NAMESPACE_BOB::solve(n);
}