#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 + 5;
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] = 1;
			else dir[i] = 0; 
		}
	}
	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;
		}
	}
}
bool vis[N];
vector<pair<bool, int> > E[N];
int Bob(const int testid, const int n) {
	mt19937 rnd(time(0));
	int s = -1;
	For(i, 1, 4000) {
		int x;
		x = rnd() % n;
		if (vis[x]) continue;
		vis[x] = 1;
		E[x] = discover(x);
		int cnt = 0;
		for (auto i : E[x]) cnt = cnt + i.y;
		if (cnt && cnt != E[x].size()) {
			s = x;
			break;
		}
	}
	if (s == -1) {
		int x = rnd() % n;
		if (!vis[x]) E[x] = discover(x), vis[x] = 1;
		while (E[x][0].y != 0) {
			x = rnd() % n;
			if (!vis[x]) E[x] = discover(x), vis[x] = 1;
		}
		s = E[x][0].x;
		if (!vis[s]) vis[s] = 1, E[s] = discover(s);
	}
	int cnt = 0;
	for (auto i : E[s]) cnt = cnt + 1 - i.y;
	while (cnt) {
		for (auto i : E[s]) {
			if (i.y == 0) {
				s = i.x;
				break;
			}
		}
		if (!vis[s]) E[s] = discover(s), vis[s] = 1;
		cnt = 0;
		for (auto i : E[s]) cnt = cnt + 1 - i.y;
	}
	return s;
}

answer.code: In function ‘int Bob(int, int)’:
answer.code:75:34: error: no match for ‘operator=’ (operand types are ‘std::vector<std::pair<bool, int> >’ and ‘std::vector<std::pair<int, bool> >’)
   75 |                 E[x] = discover(x);
      |                                  ^
In file included from /usr/include/c++/13/vector:72,
                 from /usr/include/c++/13/queue:63,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:157,
                 from answer.code:1:
/usr/include/c++/13/bits/vector.tcc:210:5: note: candidate: ‘std::vector<_Tp, _Alloc>& std::vector<_Tp, _Alloc>::operator=(const std::vector<_Tp, _Alloc>&) [with _Tp = std::pair<bool, int>; _Alloc = std::allocator<std::pair<bool, int> >]’
  210 |     vector<_Tp, _Alloc>::
      |     ^~~~~~~~~~~~~~~~~~~
/usr/include/c++/13/bits/vector.tcc:211:42: note:   no known conversion for argument 1 from ‘std::vector<std::pair<int, bool> >’ to ‘const std::vector<std::pair<bool, int> >&’
  211 |     operator=(const vector<_Tp, _Alloc>& __x)
      |               ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
In file included from /usr/include/c++/13/vector:66:
/usr/include/c++/13/bits/stl_vector.h:763:7: note: candidate: ‘std::vector<_Tp, _Alloc>& std::vector<_Tp, _Alloc>::operator=(std::vector<_Tp, _Alloc>&&) [with _Tp = std::pair<bool, int>; _Alloc = std::allocator<std::pair<bool, int> >]’
  763 |       operator=(vector&& __x) noexcept(_Alloc_traits::_S_nothrow_move())
      |       ^~~~~~~~
/usr/include/c++/13/bits/stl_vector.h:763:26: note:   no known conversion for argument 1 from ‘std::vector<std::pair<int, bool> >’ to ‘std::vector<std::pair<bool, int> >&&’
  763 |       operator=(vector&& __x) noexcept(_Alloc_traits::_S_nothrow_move())
      |                 ~~~~~~~~~^~~
/usr/include/c++/13/bits/stl_vector.h:785:7: note: candidate: ‘std::vector<_Tp, _Alloc>& std::vector<_Tp, _Alloc>::operator=(std::initializer_list<_Tp>) [with _Tp = std::pair<bool, int>; _Alloc = std::allocator<std::pair<bool, int> >]’
  785 |       operator=(initializer_list<value_type> __l)
      |       ^~~~~~~~
/usr/include/c++/13/bits/stl_vector.h:785:46: note:   no known conversion for argument 1 from ‘std::vector<std::pair<int, bool> >’ to ‘std::initializer_list<std::pair<bool, int> >’
  785 |       operator=(initializer_list<value_type> __l)
      |                 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
answer.code:85:47: error: no match for ‘operator=’ (operand types are ‘std::vector<std::pair<bool, int> >’ and ‘std::vector<std::pair<int, bool> >’)
   85 |                 if (!vis[x]) E[x] = discover(x), vis[x] = 1;
      |                                               ^
/usr/include/c++/13/bits/vector.tcc:210:5: note: candidate: ‘std::vector<_Tp, _Alloc>& std::vector<_Tp, _Alloc>::operator=(const std::vector<_Tp, _Alloc>&) [with _Tp = std::pair<bool, int>; _Alloc = std::allocator<std::pair<bool, int> >]’
  210 |     vector<_Tp, _Alloc>::
      |     ^~~~~~~~~~~~~~~~~~~
/usr/include/c++/13/bits/vector.tcc:211:42: note:   no known conversion for argument 1 from ‘std::vector<std::pair<int, bool> >’ to ‘const std::vector<std::pair<bool, int> >&’
  211 |     operator=(const vector<_Tp, _Alloc>& __x)
      |               ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
/usr/include/c++/13/bits/stl_vector.h:763:7: note: candidate: ‘std::vector<_Tp, _Alloc>& std::vector<_Tp, _Alloc>::operator=(std::vector<_Tp, _Alloc>&&) [with _Tp = std::pair<bool, int>; _Alloc = std::allocator<std::pair<bool, int> >]’
  763 |       operator=(vector&& __x) noexcept(_Alloc_traits::_S_nothrow_move())
      |       ^~~~~~~~
/usr/include/c++/13/bits/stl_vector.h:763:26: note:   no known conversion for argument 1 from ‘std::vector<std::pair<int, bool> >’ to ‘std::vector<std::pair<bool, int> >&&’
  763 |       operator=(vector&& __x) noexcept(_Alloc_traits::_S_nothrow_move())
      |                 ~~~~~~~~~^~~
/usr/include/c++/13/bits/stl_vector.h:785:7: note: candidate: ‘std::vector<_Tp, _Alloc>& std::vector<_Tp, _Alloc>::operator=(std::initializer_list<_Tp>) [with _Tp = std::pair<bool, int>; _Alloc = std::allocator<std::pair<bool, int> >]’
  785 |       operator=(initializer_list<value_type> __l)
      |       ^~~~~~~~
/usr/include/c++/13/bits/stl_vector.h:785:46: note:   no known conversion for argument 1 from ‘std::vector<std::pair<int, bool> >’ to ‘std::initializer_list<std::pair<bool, int> >’
  785 |       operator=(initializer_list<value_type> __l)
      |                 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
answer.code:88:55: error: no match for ‘operator=’ (operand types are ‘std::vector<std::pair<bool, int> >’ and ‘std::vector<std::pair<int, bool> >’)
   88 |                         if (!vis[x]) E[x] = discover(x), vis[x] = 1;
      |                                                       ^
/usr/include/c++/13/bits/vector.tcc:210:5: note: candidate: ‘std::vector<_Tp, _Alloc>& std::vector<_Tp, _Alloc>::operator=(const std::vector<_Tp, _Alloc>&) [with _Tp = std::pair<bool, int>; _Alloc = std::allocator<std...