#include "speedrun.h"
#include <bits/stdc++.h>
using namespace std;
vector<int>adj[1005];
int pp[1005];
int in[1005];
int tour[1005];
int ptr=0;
void dfs(int index, int par){
in[index]=ptr++;
tour[in[index]]=index;
for(auto it:adj[index]){
if(it==par) continue;
pp[it]=index;
dfs(it,index);
}
}
void assignHints(int subtask, int n, int a[], int b[]) {
int temp,temp2;
for(int x=1;x<=n-1;x++){
temp=a[x];
temp2=b[x];
adj[temp].push_back(temp2);
adj[temp2].push_back(temp);
}
dfs(1,-1);
setHintLen(20);
for(int x=1;x<=n;x++){
int cur=in[x];
//show2(x,x,cur,cur);
int nxt=tour[(cur+1)%n];
//show(nxt,nxt);
for(int y=1;y<=10;y++){
if(pp[x]&(1<<(y-1))){
setHint(x,y,1);
//show2(index,x,bit,y);
}
}
for(int y=1;y<=10;y++){
if(nxt&(1<<(y-1))){
setHint(x,y+10,1);
//show2(index,x,bit,y+10);
}
}
}
//show(done,1);
}
int counter=0;
void dp(int index, int sz, int target){
if(counter==sz-1) return;
int par=0;
int nxt=0;
for(int x=1;x<=10;x++){
bool hold=getHint(x);
if(hold){
par+=(1<<(x-1));
}
hold=getHint(x+10);
if(hold){
nxt+=(1<<(x-1));
}
}
//for(int x=1;x<=20;x++){
//bool hold=getHint(x);
//cout << hold;
//}
//cout << endl;
//show3(index,index,par,par,nxt,nxt);
//show(target,target);
bool amos;
if(target!=-1){
amos=goTo(target);
if(amos){
counter++;
dp(target,sz,-1);
}
else{
amos=goTo(par);
dp(par,sz,target);
}
return;
}
amos=goTo(nxt);
if(amos){
counter++;
dp(nxt,sz,-1);
}
else{
amos=goTo(par);
dp(par,sz,nxt);
}
}
void speedrun(int subtask, int N, int start) {
dp(start,N,-1);
}
