#include "treasure.h"

#include <bits/stdc++.h>
#define ms(x, v) memset(x, v, sizeof(x))
#define il __attribute__((always_inline)) static
#define U(i,l,r) for(int i(l),END##i(r);i<=END##i;++i)
#define D(i,r,l) for(int i(r),END##i(l);i>=END##i;--i)
using namespace std;
using ll = long long;

#define meow(...) fprintf(stderr, __VA_ARGS__)
#define Assert(e, v) if (!(e)) { meow("AF@%d\n", __LINE__ ); exit(v); }

#define vc vector
#define eb emplace_back
#define pb push_back

const int N = 2000006;
int n, m, x; pair<int, int> e[N];
vc<int> g[N];

const int LIM = 2000;
int dep[N], fa[N], col[N], flag[N];
void dfs(int u, int f) {
	dep[u] = dep[f] + 1; fa[u] = f;
	col[u] = (dep[u] & 1);
	flag[u] = dep[u] <= LIM;
	for (int v : g[u]) {
		if (!dep[v]) {
			dfs(v, u);
		}
	}
}
void Alice(const int testid, const int _n, const int _m, const int _x, const int _u[], const int _v[], bool dir[]) {
	n = _n; m = _m; x = _x;
	U (i, 0, m - 1) {
		e[i] = {_u[i], _v[i]};
		auto [u, v] = e[i];
		g[u].pb(v); g[v].pb(u);
	}
	dfs(x, 1);

	U (i, 0, m - 1) {
		auto [u, v] = e[i];
		if (flag[u] && flag[v]) {
			dir[i] = dep[v] < dep[u] ? 0 : 1;
		} else if (flag[v]) {
			dir[i] = 0;
		} else if (flag[u]) {
			dir[i] = 1;
		} else {
			dir[i] = col[v] ? 0 : 1;
		}
	}
	U (i, 0, m - 1) {
		auto [u, v] = e[i];
		if (dir[i]) swap(u, v);
		// clog << u << ' ' << v << endl;
	}
}

map<int, vc<pair<int, bool>>> mp;
vc<pair<int, bool>> ask(int u) {
	if (mp.find(u) != mp.end())
		return mp[u];
	return mp[u] = discover(u);
}
int go(int u, vc<pair<int, bool>> h) {
	while (1) {
		bool tag = 0;
		// clog << "!" << u << endl;
		for (auto [v, d] : h) if (d == 0) {
			u = v;
			tag = 1;
			break;
		}
		if (!tag) break;

		h = ask(u);
	}
	return u;
}
int Bob(const int testid, const int n) {
	int p[n]; U (i, 0, n - 1) p[i] = i;
	mt19937 rng(114514);
	shuffle(p, p + n, rng);

	U (_, 0, min(n - 1, LIM)) {
		int u = p[_];
		vc<pair<int, bool>> h = ask(u);

		if (h.size() > 1) {
			bool flag[2] {};
			for (auto [v, d] : h)
				flag[d] = 1;
			if (!flag[0] || !flag[1])
				continue;
			// clog << "fix " << u << endl;
			int tmp = go(u, h);
			assert(tmp == 2);
			return tmp;
		}
	}

	int u = 0; vc<pair<int, bool>> h = ask(0);
	return go(0, h);
}