#undef _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define pb push_back
#define fi first
#define si second
#define ar array
typedef pair<int,int> pi;
typedef tuple<int,int,int> ti;
void debug_out() {cerr<<endl;}
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {cerr<<" "<<to_string(H);debug_out(T...);}
#define debug(...) cerr<<"["<<#__VA_ARGS__<<"]:",debug_out(__VA_ARGS__)
#include "speedrun.h"
int N, lst;
vector<int> adj[1010];
vector<int> path;
void setchild(int u, int v) {
int tmp = v, bit = 1;
while (tmp) {
setHint(u, bit, tmp % 2);
tmp /= 2;
++bit;
}
}
void setpar(int u, int v) {
int tmp = v, bit = 11;
while (tmp) {
setHint(u, bit, tmp % 2);
tmp /= 2;
++bit;
}
}
int getchild() {
int ret = 0;
for (int i = 1; i <= 10; ++i) {
if (getHint(i) == 1) ret += (1 << (i - 1));
}
return ret;
}
int getpar() {
int ret = 0;
for (int i = 11; i <= 20; ++i) {
if (getHint(i) == 1) ret += (1 << (i - 11));
}
return ret;
}
void dfs(int x, int p) {
if (path.size()) {
setchild(path.back(), x);
setpar(x, p);
}
path.pb(x);
for (auto i: adj[x]) {
if (i == p) continue;
dfs(i, x);
}
}
void assignHints(int subtask, int _N, int A[], int B[]) { /* your solution here */
N = _N;
for (int i = 1; i < N; ++i) {
adj[A[i]].pb(B[i]);
adj[B[i]].pb(A[i]);
}
setHintLen(20);
dfs(1, 1);
}
void speedrun(int subtask, int _N, int start) { /* your solution here */
set<int> vis;
vis.insert(start);
while ((int)vis.size() != _N) {
int node = getchild();
if (node == 0) {
while (node != 1) {
node = getpar();
goTo(node);
vis.insert(node);
}
} else {
while (!goTo(node)) {
vis.insert(getpar());
goTo(getpar());
}
}
vis.insert(node);
}
}
