#include<bits/stdc++.h>
#include "speedrun.h"
using namespace std;
vector<long long>oiler;
vector<long long>graph[1'000'000];
vector<long long>tree[1'000'000];
bool vis[1'000'000];
long long par[1'000'000];
long long next1[1'000'000];
void dfs(long long x)
{
vis[x]=true;
if (oiler.size()!=0)
{
next1[oiler.back()]=x;
}
oiler.push_back(x);
for (auto next:graph[x])
{
if (!vis[next]) dfs(next);
par[next]=x;
}
return;
}
void assignHints(int subtask, int n, int a[], int b[])
{
setHintLen(20);
vector<pair<long long, long long>>v;
for (long long i=1; i<n; i++)
{
v.push_back({a[i], b[i]});
v.push_back({b[i], a[i]});
graph[a[i]].push_back(b[i]);
graph[b[i]].push_back(a[i]);
}
for (long long i=1; i<=n; i++) next1[i]=0;
dfs(1);
for (long long i=1; i<=n; i++)
{
long long x=par[i];
for (long long j=1; j<=10; j++)
{
setHint(i, j, x%2);
x/=2;
}
x=next1[i];
for (long long j=11; j<=20; j++)
{
setHint(i, j, x%2);
x/=2;
}
}
}
void speedrun(int subtask, int n, int start)
{
long long root=start;
while (root!=1)
{
long long p=0;
for (long long j=1; j<=10; j++)
{
p+=(1<<(j-1))*getHint(j);
}
goTo(p);
root=p;
}
while (true)
{
long long sled=0;
for (long long j=11; j<=20; j++)
{
sled+=(1<<(j-11))*getHint(j);
}
if (sled==0)
{
break;
}
bool ret=goTo(sled);
if (ret==0)
{
while (true)
{
long long pp=0;
for (long long j=1; j<=10; j++)
{
pp+=(1<<(j-1))*getHint(j);
}
goTo(pp);
if (goTo(sled))
{
break;
}
}
}
}
return;
}
