#include <bits/stdc++.h>
#include "speedrun.h"
using namespace std;
void dfs1(int u, int N, bool flag[]) {
for (int i = 1; i <= N; i++) {
if (getHint(i) && !flag[i]) {
flag[i] = true;
goTo(i);
dfs1(i, N, flag);
goTo(u);
}
}
}
void ass1(int N, int A[], int B[]) {
setHintLen(N);
for (int i = 1; i <= N - 1; i++) {
setHint(A[i], B[i], 1);
setHint(B[i], A[i], 1);
}
}
void ass2(int N, int A[], int B[]) {
setHintLen(20);
int cc[N + 1];
fill_n(cc, N + 1, 0);
for (int i = 1; i <= N - 1; i++) {
cc[A[i]]++;
cc[B[i]]++;
}
int p = -1;
for (int i = 1; i <= N; i++) {
if (cc[i] > 1) {
p = i;
break;
}
}
for (int i = 1; i <= N; i++) {
for (int j = 0; j < 20; j++) {
setHint(i, j + 1, (p >> j) & 1);
}
}
}
void speed1(int N, int start) {
bool flag[N + 1];
fill_n(flag, N + 1, false);
dfs1(start, N + 1, flag);
}
void speed2(int N, int start) {
int p = 0;
for (int i = 0; i < 20; i++) {
p |= (getHint(i + 1) << i);
}
goTo(p);
for (int i = 1; i <= N; i++) {
goTo(i);
goTo(p);
}
}
void assignHints(int subtask, int N, int A[], int B[]) { /* your solution here */
if (subtask == 1) {
ass1(N, A, B);
}
if (subtask == 2) {
ass2(N, A, B);
}
}
void speedrun(int subtask, int N, int start) { /* your solution here */
if (subtask == 1) {
speed1(N, start);
}
if (subtask == 2) {
speed2(N, start);
}
}
