#include "speedrun.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
void assignHints(int subtask, int N, int A[], int B[]) { /* your solution here */
vector<vector<int>> adj(N+1);
FOR(i,1,N){
adj[A[i]].pb(B[i]);
adj[B[i]].pb(A[i]);
}
vector<int> arr;
vector<int> visited(N+1);
stack<int> s;
s.push(1);
vector<int> par(N+1);
while (!s.empty()){
int current = s.top();
s.pop();
if (visited[current]) continue;
arr.pb(current);
for (auto x: adj[current]){
s.push(x);
if (!visited[x]) par[x] = current;
}
visited[current] = 1;
}
setHintLen(20);
// arr.pb(0);
FOR(i,0,N){
// int k = 0;
int d = arr[(i+1)%N];
FOR(j,0,10){
if (par[arr[i]] & (1 << j)){
// k |= (1 << j);
setHint(arr[i], j+1, 1);
}else{
setHint(arr[i], j+1, 0);
}
if (d & (1 << j)){
// k |= (1 << (j+10));
setHint(arr[i], j+11, 1);
}else{
setHint(arr[i], j+11, 0);
}
}
}
// for (int x: arr) cout << x << " ";
// cout << endl;
return;
}
void speedrun(int subtask, int N, int start) { /* your solution here */
vector<int> visited(N+1);
int c = 0;
int u = 0;
while (start != 1){
// u++;
// if (u > 5) break;
int par = 0;
FOR(i,1,11){
if (getHint(i)) par |= (1 << (i-1));
}
goTo(par);
// cout << start << par << endl;
start = par;
}
int current = start;
int curtogo = 0;
int o = 0;
while (c < N){
o++;
// if (o > 40) break;
int ne = 0;
int par = 0;
FOR(i,1,11){
if (getHint(i)) par |= (1 << (i-1));
}
FOR(i,11,21){
if (getHint(i)) ne |= (1 << (i-1-10));
}
if (!visited[current]){
c++;
visited[current] = 1;
}
// cout << current << curtogo << endl;
if (curtogo){
// visited[current] = 1;
bool can = goTo(curtogo);
if (can){
current = curtogo;
curtogo = 0;
}else{
goTo(par);
current = par;
}
}else{
if (!visited[ne]){
bool can = goTo(ne);
if (can){
current = ne;
curtogo = 0;
}else{
goTo(par);
curtogo = ne;
}
}else{
goTo(par);
current = par;
curtogo = 0;
}
}
}
}
