#include <bits/stdc++.h>
#include "speedrun.h"
using namespace std;
/// de comentat
/*
string s[1001];
vector <int> mc[1001];
void setHintLen (int x)
{
//
}
void setHint (int i, int j, int b)
{
if (b == 1)
{
s[i] += '1';
}
else
{
s[i] += '0';
}
}
bool getHint (int i, int j)
{
if (s[i][j - 1] == '1')
{
return true;
}
return false;
}
bool goTo(int nod, int x)
{
for (auto f : mc[nod])
{
if (f == x)
{
return true;
}
}
return false;
}
*/
/// de inclus in cod
const int max_size = 1e3 + 1;
int dfstree[max_size], poz, t[max_size];
vector <int> mc[max_size];
void dfs (int nod, int par)
{
t[nod] = par;
dfstree[++poz] = nod;
for (auto f : mc[nod])
{
if (f == par)
{
continue;
}
dfs(f, nod);
}
}
void assignHints (int subtask, int N, int A[], int B[])
{
setHintLen(20);
for (int i = 1; i < N; i++)
{
mc[A[i]].push_back(B[i]);
mc[B[i]].push_back(A[i]);
}
dfs(1, 0);
/// primii 10 biti pentru tata, ult 10 biti pt poz
for (int i = 1; i <= N; i++)
{
int x = t[i];
for (int j = 0; j < 10; j++)
{
if ((x & (1 << j)) != 0)
{
setHint(i, j + 1, 1);
}
else
{
setHint(i, j + 1, 0);
}
}
}
for (int i = 1; i < N; i++)
{
int x = dfstree[i], y = dfstree[i + 1];
for (int j = 0; j < 10; j++)
{
if ((y & (1 << j)) != 0)
{
setHint(x, 10 + j + 1, 1);
}
else
{
setHint(x, 10 + j + 1, 0);
}
}
}
int x = dfstree[N], y = dfstree[1];
for (int j = 0; j < 10; j++)
{
if ((y & (1 << j)) != 0)
{
setHint(x, 10 + j + 1, 1);
}
else
{
setHint(x, 10 + j + 1, 0);
}
}
}
void speedrun (int subtask, int N, int start )
{
int nod = start;
for (int i = 1; i < N; i++)
{
int urm = 0;
for (int j = 11; j <= 20; j++)
{
int x = getHint(j);
if (x == 1)
{
urm += (1 << (j - 11));
}
}
//cout << urm << " ";
while (!goTo(urm))
{
int par = 0;
for (int j = 1; j <= 10; j++)
{
int x = getHint(j);
if (x == 1)
{
par += (1 << (j - 1));
}
}
bool x = goTo(par);
nod = par;
}
bool x = goTo(urm);
nod = urm;
// cout << nod << " ";
}
return;
}
