#include "speedrun.h"
#include<bits/stdc++.h>
using namespace std;
inline bool getbit(int num, int bit)
{
return (num >> bit)&1;
}
vector<int> ad[1005];
bool visited[1005];
void dfs(int u, int par)
{
visited[u] = 1;
vector<int> child;
for(int v : ad[u]) if(visited[v] == 0) child.push_back(v);
for(int v : child) dfs(v, u);
//Set for u
int val = 0; if(child.size() > 0) val = child[0];
for(int i = 0; i < 10; i++) setHint(u, i+1, getbit(val, i));
if(child.size() > 0){
for(int i = 0; i+1 < child.size(); i++){
int v = child[i], x = child[i+1];
for(int j = 0; j < 10; j++) setHint(v, j+11, getbit(x, j));
}
int v = child.back(), x = par;
for(int j = 0; j < 10; j++) setHint(v, j+11, getbit(x, j));
}
visited[u] = 0;
}
void assignHints(int subtask, int n, int A[], int B[]){
for(int i = 1; i <= n; i++) ad[i].clear();
for(int i = 1; i < n; i++){
ad[A[i]].push_back(B[i]);
ad[B[i]].push_back(A[i]);
}
setHintLen(20); dfs(1, 0);
}
int getval(int l, int r)
{
int ans = 0;
for(int i = l; i <= r; i++) if(getHint(i) == 1) ans += (1 << (i-l));
return ans;
}
void dfs_solve(int u, int n, bool first_node)
{
visited[u] = 1;
int v = getval(1, 10);
if(v == 0){
if(first_node == 1){
for(int i = 1; i <= n; i++) if(goTo(i) == 1) dfs_solve(i, n, 0);
}
return;
}
while(true){
if(visited[v] == 0){
if(goTo(v) == 0) break;
dfs_solve(v, n, 0);
goTo(u);
}
goTo(v);
v = getval(11, 20);
goTo(u);
}
}
void speedrun(int subtask, int n, int start) { /* your solution here */
//Do some dfs
memset(visited, 0, sizeof(visited));
dfs_solve(start, n, 1);
}
