#include <bits/stdc++.h>
#include "speedrun.h"
using namespace std;
const int kN = 1e3;
int par[1 + kN];
vector<int> g[1 + kN];
vector<int> order;
void dfs(int u) {
order.emplace_back(u);
for (int v : g[u]) {
if (v != par[u]) {
par[v] = u;
dfs(v);
}
}
}
void assignHints(int subtask, int N, int A[], int B[]) {
int lg = 0;
while (1 << (lg + 1) <= N) {
lg += 1;
}
lg += 1;
setHintLen(2 * lg);
for (int i = 1; i < N; ++i) {
g[A[i]].emplace_back(B[i]);
g[B[i]].emplace_back(A[i]);
}
dfs(1);
for (int i = 0; i < N; ++i) {
int v = order[i];
for (int bit = 0; bit < lg; ++bit) {
if (par[v] & (1 << bit)) {
setHint(v, 1 + bit, true);
}
if (i < N - 1 && (order[i + 1] & (1 << bit))) {
setHint(v, lg + 1 + bit, true);
}
}
}
}
int getPar(int x, int lg) {
int res = 0;
for (int bit = 0; bit < lg; ++bit) {
if (getHint(bit + 1)) {
res += (1 << bit);
}
}
return res;
}
int getNext(int x, int lg) {
int res = 0;
for (int bit = 0; bit < lg; ++bit) {
if (getHint(lg + 1 + bit)) {
res += (1 << bit);
}
}
return res;
}
void speedrun(int subtask, int N, int start) {
int lg = getLength(), curr = start;
while (curr != 1) {
int p = getPar(curr, lg);
goTo(p);
curr = p;
}
int nxt = getNext(curr, lg);
while (nxt) {
if (!goTo(nxt)) {
goTo(getPar(curr, lg));
} else {
curr = nxt;
nxt = getNext(curr, lg);
}
}
}
