#include "speedrun.h"
using namespace std;
#include <vector>
#include <set>
#include <iostream>
const int NMAX = 1001;
vector <int> adj[NMAX + 1];
int dfsTime = 0;
int par[NMAX + 1];
int lin[NMAX + 1];
void dfs(int node, int parent){
par[node] = parent;
lin[++dfsTime] = node;
for(int 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 - 1; i++){
adj[A[i]].push_back(B[i]);
adj[B[i]].push_back(A[i]);
}
setHintLen(20);
dfs(1, 0);
lin[N + 1] = lin[1];
for(int i = 1; i <= N; i++){
for(int j = 0; j < 10; j++){
setHint(lin[i], j + 1, par[lin[i]] & (1 << j));
setHint(lin[i], j + 1 + 10, lin[i + 1] & (1 << j));
}
}
}
void speedrun(int subtask, int N, int start){
int node = start;
for(int i = 1; i <= N - 1; i++){
int p = 0, x = 0;
for(int i = 1; i <= 10; i++){
p += (1 << (i - 1)) * getHint(i);
x += (1 << (i - 1)) * getHint(i + 10);
}
while(!goTo(x)){
node = p;
goTo(node);
p = 0;
for(int i = 1; i <= 10; i++){
p += (1 << (i - 1)) * getHint(i);
}
}
node = x;
}
}
