#include <bits/stdc++.h>
#include "treasure.h"
using namespace std;
#define x first
#define y second
#define mp(Tx, Ty) make_pair(Tx, Ty)
#define For(Ti, Ta, Tb) for(auto Ti = (Ta); Ti <= (Tb); Ti++)
#define Dec(Ti, Ta, Tb) for(auto Ti = (Ta); Ti >= (Tb); Ti--)
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define range(Tx) begin(Tx),end(Tx)
const int N = 5e6;
int d[N];
int h[N], e[N * 2], ne[N * 2], w[N * 2], idx;
void add(int a, int b, int c) {
	e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}

void Alice(const int testid, const int n, const int m, const int x, const int u[], const int v[], bool dir[]) {
	memset(h, -1, sizeof(h));
	memset(d, 0, sizeof(d));
	For(i, 0, m - 1) {
		add(u[i], v[i], i), add(v[i], u[i], i);
	}
	queue<int> q;
	q.push(x);
	d[x] = 1;
	while (q.size()) {
		int t = q.front();
		q.pop();
		for (int i = h[t]; ~i; i = ne[i]) {
			int j = e[i];
			if (d[j]) continue;
			int id = w[i];
			if (u[id] == t) {
				d[v[id]] = d[t] + 1;
				q.push(v[id]);
			} else {
				d[u[id]] = d[t] + 1;
				q.push(u[id]);
			}
		}
	}
	int k = 1000;
	For(i, 0, m - 1) {
		if (d[u[i]] <= k && d[v[i]] <= k) {
			if (d[u[i]] < d[v[i]]) dir[i] = 0;
			else dir[i] = 1; 
		}
	}
	For(i, 0, m - 1) {
		if (d[u[i]] <= k && d[v[i]] > k) {
			dir[i] = 1;
		}
		if (d[u[i]] > k && d[v[i]] <= k) {
			dir[i] = 0;
		}
	}
	For(i, 0, m - 1) {
		if (d[u[i]] > k && d[v[i]] > k) {
			if (d[u[i]] % 2 == 0) dir[i] = 1;
			else dir[i] = 0;
		}
	}
}

int Bob(const int testid, const int n) {
	mt19937 rnd(time(0));
	int s = -1;
	vector<pair<int, bool> > e;
	For(i, 1, 4000) {
		int x = rnd() % n;
		e = discover(x);
		int cnt = 0;
		for (auto i : e) cnt = cnt + i.y;
		if (cnt != e.size()) {
			s = x;
			break;
		}
	}
	if (s == -1) {
		int x = rnd() % n;
		e = discover(x);
		while (e[0].y != 0) {
			x = rnd() % n;
			e = discover(x);
		}
		return e[0].x;
	}
	int cnt = 0;
	for (auto i : e) cnt = cnt + 1 - i.y;
	while (cnt) {
		for (auto i : e) {
			if (i.y == 0) {
				s = i.x;
				break;
			}
		}
		e = discover(s);
		cnt = 0;
		for (auto i : e) cnt = cnt + 1 - i.y;
	}
	return s;
}