#include <bits/stdc++.h>
using namespace std;
#include "speedrun.h"
int S[1005], back[1005], cnt = 1;
vector <int> adj[1005];
void dfs(int x, int par){
S[x] = cnt++;
for(int i = 0; i < 10; i++)if(par >> i & 1)setHint(x, i + 1, 1);
for(auto i : adj[x]){
if(i == par)continue;
dfs(i, x);
}
}
void assignHints(int subtask, int N, int A[], int B[]) { /* your solution here */
setHintLen(20);
for(int i = 1; i <= N - 1; i++)adj[A[i]].push_back(B[i]), adj[B[i]].push_back(A[i]);
dfs(1, 0);
for(int i = 1; i <= N; i++)back[S[i]] = i;
for(int i = 1; i <= N; i++){
int x = back[S[i] + 1];
for(int j = 0; j < 10; j++)if(x >> j & 1)setHint(i, j + 11, 1);
}
}
int vis[1005];
void bruh(int x, int par, set <int> &pos){
vis[x] = 1;
int cnt = 0;
for(int i = 11; i <= 20; i++)if(getHint(i))cnt += (1ll << (i - 11));
int cnt2 = 0;
for(int i = 1; i <= 10; i++)if(getHint(i))cnt2 += (1ll << (i - 1));
set <int> cry;
if(!vis[cnt]){
bool ok = goTo(cnt);
if(ok)bruh(cnt, x, pos);
else pos.insert(cnt), cry.insert(cnt);
}
while(1){
bool f = 0;
for(auto i : pos){
if(cry.find(i) != cry.end())continue;
cry.insert(i);
if(vis[i])continue;
bool ok = goTo(i);
if(ok){
int tmp = i;
pos.erase(i);
bruh(tmp, x, pos);
f = 1;
break;
}
}
if(!f)break;
}
if(!vis[cnt2]){
bool ok = goTo(cnt2);
if(ok)bruh(cnt2, x, pos);
}
if(par != -1)goTo(par);
}
void speedrun(int subtask, int N, int start) { /* your solution here */
set <int> br;
vis[0] = vis[N + 1] = 1;
bruh(start, -1, br);
}
