#include "speedrun.h"
#include <bits/stdc++.h>
using namespace std;
void dfs(int v, vector<int> &ord, vector<int> &pr, vector<vector<int>> &g) {
ord.push_back(v);
for (auto u : g[v]) {
if (u != pr[v]) {
pr[u] = v;
dfs(u, ord, pr, g);
}
}
}
void assignHints(int subtask, int n, int a[], int b[]) {
vector<vector<int>> g(n);
for (int i = 1; i < n; ++i) {
a[i]--, b[i]--;
g[a[i]].push_back(b[i]);
g[b[i]].push_back(a[i]);
}
vector<int> ord, pr(n);
dfs(0, ord, pr, g);
setHintLen(20);
for (int i = 0; i < (int)ord.size(); ++i) {
for (int j = 0; j < 10; ++j) {
setHint(ord[i] + 1, j + 1, (pr[ord[i]] >> j) & 1);
}
int nxt = ord[(i + 1) % n];
for (int j = 0; j < 10; ++j) {
setHint(ord[i] + 1, 10 + j + 1, (nxt >> j) & 1);
}
}
}
void speedrun(int subtask, int n, int start) {
start--;
int nw = start;
set<int> used;
while (nw != 0) {
used.insert(nw);
int pr = 0;
for (int j = 0; j < 10; ++j) {
if (getHint(j + 1)) {
pr += (1 << j);
}
}
goTo(pr + 1);
nw = pr;
}
used.insert(nw);
vector<int> st = {nw};
while (used.size() != n) {
int nxt = 0;
for (int j = 0; j < 10; ++j) {
if (getHint(10 + j + 1)) {
nxt += (1 << j);
}
}
while (!goTo(nxt + 1)) {
st.pop_back();
goTo(st.back() + 1);
}
st.push_back(nxt);
nw = nxt;
used.insert(nw);
}
}
