#include <bits/stdc++.h>
#include "speedrun.h"
using namespace std;
const int maxn = 1e3 + 2;
// bool ad [maxn][maxn];
void assignHints(int subtask, int N, int A[], int B[]) { /* your solution here */
int deg [N + 1] = {};
vector <int> ad [maxn];
if (subtask == 1 || N <= 4) {
setHintLen(N);
for (int i = 1; i < N; i++){
setHint(A[i], B[i], 1);
setHint(B[i], A[i], 1);
}
}
if (subtask == 2) {
setHintLen(1);
for (int i = 1; i < N; i++){
deg[A[i]]++;
deg[B[i]]++;
}
for (int i = 1; i <= N; i++){
if (deg[i] > 1) setHint(i, 1, 1);
}
}
if (subtask == 3) {
setHintLen(20);
for (int i = 1; i < N; i++){
ad[A[i]].push_back(B[i]);
ad[B[i]].push_back(A[i]);
}
for (int i = 1; i <= N; i++){
// cout << i << ": ";
for (int j = 0; j < ad[i].size(); j++){
int k = ad[i][j];
int offset = j * 10 + 1;
for (int b = 0; b <= 9; b++) {
// cout << !!(k & (1 << b));
setHint(i, b + offset, !!(k & (1 << b)));
}
// cout << " ";
}
// cout << "\n";
}
}
}
void speedrun(int subtask, int N, int start) { /* your solution here */
if (subtask == 1 || N <= 4) {
int vis [N + 1] = {};
auto dfs = [&] (int u, int p = -1, auto&& dfs) -> void {
for (int i = 1; i <= N; i++){
if (i == p || i == start) continue;
if (getHint(i)) {
goTo(i);
dfs(i, u, dfs);
}
}
if (p != -1) goTo(p);
};
dfs(start, -1, dfs);
}
if (subtask == 2) {
if (!getHint(1)) {
for (int i = 1; i <= N; i++){
if (goTo(i)) {
start = i;
break;
}
}
}
for (int i = 1; i <= N; i++){
if (i == start) continue;
goTo(i);
goTo(start);
}
}
if (subtask == 3) {
int vis [N + 1] = {};
auto dfs = [&] (int u, int p = -1, auto&& dfs) -> void {
int v1 = 0, v2 = 0;
for (int i = 0; i <= 9; i++){
v1+=((1 << i) * getHint(i + 1));
v2+=((1 << i) * getHint(i + 11));
}
// cout << u << " " << v1 << " " << v2 << "\n";
if (v1 && v1 != p) {
goTo(v1);
dfs(v1, u, dfs);
goTo(u);
}
if (v2 && v2 != p) {
goTo(v2);
dfs(v2, u, dfs);
goTo(u);
}
// for (int i = 1; i <= N; i++){
// if (i == p || i == start) continue;
// if (getHint(i)) {
// goTo(i);
// dfs(i, u, dfs);
// }
// }
// if (p != -1) goTo(p);
};
dfs(start, -1, dfs);
}
}
