#include <bits/stdc++.h>
#include "speedrun.h"
using namespace std;
vector <int> adj[1005];
vector <int> prevv;
vector <int> dfs_ord;
void dfs(int node, int parent){
dfs_ord.push_back(node);
prevv[node]=parent;
for (auto child : adj[node]){
if (child!=parent){
dfs(child,node);
}
}
}
void assignHints(int subtask, int N, int A[], int B[]){
for (int i=1; i<=N; i++){
adj[i].clear();
}
prevv.assign(1005, 0);
dfs_ord.clear();
for (int i=1; i<N; i++){
adj[A[i]].push_back(B[i]);
adj[B[i]].push_back(A[i]);
}
dfs(1,0);
setHintLen (20);
for (int i=1; i<=N; i++){
for (int j=0; j<10; j++){
if (prevv[i] & (1<<j)){
setHint(i,j+1,1);
}
}
}
dfs_ord.push_back(0);
for (int i=0; i<N; i++){
int node = dfs_ord[i];
int nxt = dfs_ord[i+1];
for (int j=0; j<10; j++){
if (nxt & (1<<j)){
setHint(node,j+11,1);
}
}
}
}
void speedrun(int subtask, int N, int start){
while (start!=1){
int parent=0;
for (int j=0; j<10; j++){
if (getHint(j+1)){
parent += (1<<j);
}
}
start=parent;
goTo(parent);
}
vector <int> ls;
ls.push_back(1);
while (ls.size()){
int nxt=0;
for (int j=0; j<10; j++){
if (getHint(j+11)){
nxt += (1<<j);
}
}
if (nxt==0){return;}
if (!goTo(nxt)){
ls.pop_back();
if (ls.size()){
goTo(ls[ls.size()-1]);
}
else{return;}
}
else{ls.push_back(nxt);}
}
return;
}
