#include <bits/stdc++.h>
#ifdef MINA
#include "grader.cpp"
#endif
#include "speedrun.h"
using namespace std;
typedef int64_t ll;
void assignHints(int subtask, int n, int a[], int b[]) {
if (subtask == 1) {
vector<int> adj[n + 1];
for (int i = 1; i < n; i++) {
adj[a[i]].push_back(b[i]);
adj[b[i]].push_back(a[i]);
}
setHintLen(n);
for (int i = 1; i <= n; i++) {
for (auto nxt : adj[i]) {
setHint(i, nxt, 1);
}
}
} else if (subtask == 2) {
vector<int> adj[n + 1];
for (int i = 1; i < n; i++) {
adj[a[i]].push_back(b[i]);
adj[b[i]].push_back(a[i]);
}
setHintLen(11);
for (int i = 1; i <= n; i++) {
if (adj[i].size() == 1) {
int v = adj[i][0];
for (int b = 0; b < 10; b++) {
if ((v >> b) & 1) {
setHint(i, b + 1, 1);
}
}
} else {
setHint(i, 11, 1);
}
}
} else if (subtask == 3) {
vector<int> adj[n + 1];
for (int i = 1; i < n; i++) {
adj[a[i]].push_back(b[i]);
adj[b[i]].push_back(a[i]);
}
setHintLen(20);
for (int i = 1; i <= n; i++) {
for (int j = 0; j < adj[i].size(); j++) {
int v = adj[i][j];
for (int b = 0; b < 10; b++) {
if ((v >> b) & 1) {
setHint(i, 10 * j + b + 1, 1);
}
}
}
}
}
}
void dfs3(int i, int par, int n) {
for (int j = 0; j < 2; j++) {
int v = 0;
for (int b = 0; b < 10; b++) {
if (getHint(10 * j + b + 1)) {
v |= 1 << b;
}
}
if (v && v != par) {
goTo(v);
dfs3(v, i, n);
}
}
if (par) goTo(par);
}
void dfs(int i, int par, int n) {
for (int nxt = 1; nxt <= n; nxt++) {
if (nxt == par) continue;
if (getHint(nxt)) {
goTo(nxt);
dfs(nxt, i, n);
}
}
if (par) goTo(par);
}
void dfs2(int i, int par, int n) {
if (getHint(11)) {
for (int nxt = 1; nxt <= n; nxt++) {
if (nxt == par || nxt == i) continue;
goTo(nxt);
dfs2(nxt, i, n);
}
if (par) goTo(par);
} else {
int nxt = 0;
for (int b = 0; b < 10; b++) {
if (getHint(b + 1)) nxt |= 1 << b;
}
goTo(nxt);
if (nxt != par) {
dfs2(nxt, i, n);
}
}
}
void speedrun(int subtask, int n, int start) {
if (subtask == 1) {
dfs(start, 0, n);
} else if (subtask == 2) {
dfs2(start, 0, n);
} else if (subtask == 3) {
dfs3(start, 0, n);
}
}
