#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T> void check_min(T &a, const T &b){ a = (a < b) ? a : b; }
template<class T> void check_max(T &a, const T &b){ a = (a > b) ? a : b; }
#define all(x) (x).begin(), (x).end()
void setHintLen (int l);
void setHint(int i, int j, bool b);
int getLength ();
bool getHint(int j);
bool goTo(int x);
const int N = 1000 + 3;
vector<int> adj[N], order;
int p[N], n;
void setNumber(int i, bool second, int num){
for(int j = 0; j < 10; ++j)
setHint(i, 10 * second + j + 1, (num >> j) & 1);
}
void dfs(int u, int par){
order.push_back(u);
p[u] = par;
for(int to: adj[u]){
if(to == par) continue;
dfs(to, u);
}
}
void assignHints(int subtask, int _n, int a[], int b[]){
setHintLen(20);
n = _n;
for(int i = 1; i < n; ++i){
adj[a[i]].push_back(b[i]);
adj[b[i]].push_back(a[i]);
}
dfs(1, 1);
for(int i = 0; i < n; ++i){
int x = order[i];
setNumber(x, 0, p[x]);
if(i == n - 1) setNumber(x, 1, x);
else setNumber(x, 1, order[i + 1]);
}
}
int getNumber(bool second){
int result = 0;
for(int j = 0; j < 10; ++j)
result += ((int)getHint(10 * second + j + 1)) << j;
return result;
}
void speedrun(int subtask, int _n, int start){
n = _n;
while(start != 1)
goTo(start = getNumber(0));
while(getNumber(1) != start){
int nxt = getNumber(1);
while(!goTo(nxt))
goTo(start = getNumber(0));
start = nxt;
}
}
