#include "speedrun.h"
#include <bits/stdc++.h>
#include <vector>
#include <stack>
using namespace std;
const int NMAX = 1001;
vector<int> adj[NMAX];
stack<int> ord;
void setPar (int nod , int par)
{
int bit = 1;
while (par)
{
setHint(nod , bit , par&1);
bit++;
par /= 2;
}
}
void setNext (int nod , int nxt)
{
int bit = 11;
while (nxt)
{
setHint(nod , bit , nxt&1);
bit++;
nxt /= 2;
}
}
void dfs (int nod = 1 , int par = 0)
{
ord.push(nod);
for (auto& to : adj[nod])
{
if (to == par) continue;
setPar(to , nod);
dfs(to , nod);
}
}
void assignHints(int subtask, int N, int A[], int B[])
{
setHintLen(20);
for (int i = 1; i < N; i++)
{
adj[A[i]].push_back(B[i]);
adj[B[i]].push_back(A[i]);
}
dfs();
int prev = 1;
while (ord.size())
{
setNext(ord.top() , prev);
prev = ord.top();
ord.pop();
}
}
int getPar (int nod)
{
int par = 0;
for (int bit = 10; bit > 0; bit--)
{
par = (par << 1) + getHint(bit);
}
return par;
}
int getNext (int nod)
{
int nxt = 0;
for (int bit = 20; bit > 10; bit--)
{
nxt = (nxt << 1) + getHint(bit);
}
return nxt;
}
void speedrun(int subtask, int N, int start)
{
vector<bool> viz(N+1, 0);
int visited = 1;
int crt = start;
viz[crt] = 1;
while (visited < N)
{
int nxt = getNext(crt);
while (goTo(nxt) == 0)
{
int par = getPar(crt);
goTo(par);
crt = par;
}
crt = nxt;
visited++;
viz[crt] = 1;
}
}
