#include "speedrun.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 1024;
vector<int> G[N]; int p[N];
vector<int> preord;
int getHintL(int i){
int ret = 0;
for(int j = 0; j < 10; j++){
ret += getHint(i * 10 + j + 1) * (1 << j);
}
return ret;
}
void setHintL(int v, int i, int val){
for(int j = 0; j < 10; j++){
setHint(v, i * 10 + j + 1, (val & (1 << j)) > 0);
}
}
void dfs(int v, int pa = -1){
preord.push_back(v);
for(auto i : G[v]){
if(i != pa){
dfs(i, v); setHintL(i, 0, v);
}
}
}
int nxt = 1;
void dfs2(int v, int pa = -1){
nxt = getHintL(1);
while(nxt != 0x3ff){
if(!goTo(nxt)) {
goTo(getHintL(0));
return;
} else {
dfs2(nxt, v);
}
}
}
void assignHints(int subtask, int N, int A[], int B[]) {
setHintLen(20);
for(int i = 1; i <= N - 1; i++){
G[A[i]].push_back(B[i]);
G[B[i]].push_back(A[i]);
}
setHintL(1, 0, 0x3ff); dfs(1);
for(int i = 0; i < N - 1; i++) setHintL(preord[i], 1, preord[i + 1]);
setHintL(preord[N - 1], 1, 0x3ff);
}
void speedrun(int subtask, int N, int start) {
int x = getHintL(0);
while(x != 0x3ff) {
goTo(x); x = getHintL(0);
}
dfs2(start);
}
