#include "speedrun.h"
#include <bits/stdc++.h>
constexpr int LG = 10;
void dfs(
int node,
std::vector<int> &par,
std::vector<int> &id,
std::vector<int> &t,
const std::vector<std::vector<int>> &adj
) {
t.push_back(node);
id[node] = static_cast<int>(t.size()) - 1;
for (int i : adj[node]) {
if (i == par[node]) {
continue;
}
par[i] = node;
dfs(i, par, id, t, adj);
}
}
void assignHints(int /*subtask*/, int N, int A[], int B[]) {
if (N <= 20) {
setHintLen(1);
return;
}
const int n = N;
std::vector<std::vector<int>> adj(n + 1);
for (int i = 1; i < n; ++i) {
adj[A[i]].push_back(B[i]);
adj[B[i]].push_back(A[i]);
}
std::vector<int> par(n + 1, -1), id(n + 1, -1), t;
dfs(1, par, id, t, adj);
setHintLen(2 * LG);
for (int i = 1; i <= n; ++i) {
if (par[i] != -1) {
for (int j = 0; j < LG; ++j) {
setHint(i, j, ((1 << j) & par[i]) != 0);
}
}
if (id[i] != n - 1) {
int nxt = t[id[i] + 1];
for (int j = 0; j < LG; ++j) {
setHint(i, j + LG, ((1 << j) & nxt) != 0);
}
}
}
}
int get_par() {
int ans = 0;
for (int j = 0; j < LG; ++j) {
if (getHint(j)) {
ans |= 1 << j;
}
}
return ans;
}
int get_nxt() {
int ans = 0;
for (int j = 0; j < LG; ++j) {
if (getHint(j + LG)) {
ans |= 1 << j;
}
}
return ans;
}
void dfs_small(int node, int par, int n) {
for (int i = 1; i <= n; ++i) {
if (i != par && goTo(i)) {
dfs_small(i, node, n);
}
}
if (par != -1) {
bool b = goTo(par);
assert(b);
}
}
void speedrun(int /*subtask*/, int N, int start) {
if (N <= 20) {
dfs_small(start, -1, N);
return;
}
const int n = N;
int node = start;
while (node != 1) {
node = get_par();
bool b = goTo(node);
assert(b);
}
std::stack<int, std::vector<int>> st;
st.push(1);
for (int i = 1; i < n; ++i) {
int nxt = get_nxt();
while (!st.empty()) {
if (goTo(nxt)) {
st.push(nxt);
break;
}
st.pop();
bool b = goTo(st.top());
assert(b);
}
}
}