#include "speedrun.h"
#include <bits/stdc++.h>
using namespace std;
void assignHints(int subtask , int N, int A[], int B[]) {
if(subtask == 1) {
setHintLen(N);
for(int i = 0; i < N-1; i++) {
setHint(A[i], B[i], 1);
setHint(B[i], A[i], 1);
}
} else if(subtask == 2) {
setHintLen(20);
int deg[N], rt = 0;
memset(deg, 0, sizeof(deg));
for(int i = 0; i < N-1; i++) {
deg[A[i]-1]++; deg[B[i]-1]++;
if(deg[A[i]-1] == 2) {
rt = A[i]-1; break;
} else if(deg[B[i]-1] == 2) {
rt = B[i]-1; break;
}
}
int pow = 1;
while(rt > 0) {
for(int i = 0; i < N; i++) setHint(i+1, pow, rt%2);
rt /= 2;
pow++;
}
}
}
int n;
bool v[1000];
void dfs(int x, int par) {
v[x] = 1;
for(int i = 0; i < n; i++) {
if(getHint(i+1) == 1 && !v[i]) {
goTo(i+1);
dfs(i, x);
}
}
if(par != -1) goTo(par+1);
}
void speedrun(int subtask , int N, int start) {
if(subtask == 1) {
n = N;
memset(v, 0, sizeof(v));
dfs(start-1, -1);
} else if(subtask == 2) {
int rt = 1;
for(int i = 1; i <= 20; i++) rt += getHint(i) * pow(2, i-1);
if(rt != start) goTo(rt);
for(int i = 0; i < N; i++) {
if(i+1 == rt) continue;
goTo(i+1); goTo(rt);
}
}
}
