#include "speedrun.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
vector<int>adj[1002];
vector<int>ord;
int p[1002];
void euler(int cur,int par){
ord.push_back(cur);
p[cur]=par;
for(auto x : adj[cur]){
if(x==par)continue;
euler(x,cur);
}
}
void assignHints(int subtask, int n, int A[], int B[]) { /* your solution here */
setHintLen(20);
for(int q=1;q<n;q++){
adj[A[q]].push_back(B[q]);
adj[B[q]].push_back(A[q]);
}
euler(1,0);
// set hint : par nxt
for(int q=0;q<ord.size();q++){
int brp=0;
if(q==ord.size()-1){
brp=p[ord[q]];
}
else{
brp=p[ord[q]];
brp+=ord[q+1]*(1<<10);
}
for(int w=19;w>=0;w--){
if((brp>>w)&1){
setHint(ord[q],w+1,1);
}
}
}
}
int brp(){
int val=0;
for(int q=19;q>=0;q--){
if(getHint(q+1)){
val+=(1<<q);
}
}
return val;
}
void speedrun(int subtask, int N, int start) { /* your solution here */
// cout<<start<<" "<<brp()<<endl;
while(start!=1){
int val=brp();
goTo((val & 1023));
start=(val & 1023);
}
int cur=1;
while(true){
int val=brp();
int nxt=(val>>10);
if(nxt==0)break;
while(!goTo(nxt)){
int par=(val & 1023);
goTo(par);
val=brp();
}
cur=nxt;
}
}
