#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;
    }
}