#include <bits/stdc++.h>
#include "speedrun.h"
using namespace std;
 
const int MAXN = 1 << 10;
 
int tim = 0;
int par[MAXN], order[MAXN];
vector <int> Adj[MAXN];
 
void DFS(int node, int p = 0)
{
	tim++;
	order[tim] = node;
	par[node] = p;
	for(auto x : Adj[node])
	{
		if(x == p)
		{
			continue;
		}
		DFS(x, node);
	}
}
 
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(1);
	for(int i = 1; i <= N; i++)
	{
		int tmp = order[i + 1] + MAXN * par[order[i]];
		for(int j = 0; j < 20; j++)
		{
			int bit = (tmp >> j) & 1;
			setHint(order[i], j + 1, bit);
		}
	}
}
 
void speedrun(int subtask, int N, int start) 
{
	while(true)
	{
		int tmp = 0;
		for(int j = 1; j <= 20; j++)
		{
			if(getHint(j))
			{
				tmp |= (1 << (j - 1));
			}
		}
		if(tmp / MAXN)
		{
			goTo(tmp / MAXN);
			start = tmp / MAXN;
		}
		else
		{
			break;
		}
	}
	while(true)
	{
		int tmp = 0;
		for(int j = 1; j <= 20; j++)
		{
			if(getHint(j))
			{
				tmp |= (1 << (j - 1));
			}
		}
		int zz = tmp % MAXN;
		if(zz)
		{
			while(true)
			{
				int tt = 0;
				for(int j = 1; j <= 20; j++)
				{
					if(getHint(j))
					{
						tt |= (1 << (j - 1));
					}
				}
				if(goTo(zz))
				{
					start = zz;
					break;
				}
				start = tt / MAXN;
				goTo(start);
			}
		}
		else
		{
			break;
		}
	}
}