#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";
}
}
if (subtask == 4) {
setHintLen(316);
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++){
for (int j: ad[i]) {
setHint(i, j / 4 + 1, 1);
}
}
}
if (subtask == 5) { // left child right sibling ... left|right|parent
setHintLen(20);
for (int i = 1; i < N; i++){
ad[A[i]].push_back(B[i]);
ad[B[i]].push_back(A[i]);
}
vector <int> bt [maxn];
int l[maxn] = {}, r [maxn] = {}, pr[maxn] = {};
auto dfs = [&] (int i, int p, auto&& dfs) -> void {
for (int j = 0; j < ad[i].size(); j++){
if (ad[i][j] == p) {
ad[i].erase(ad[i].begin() + j);
break;
}
}
if (!ad[i].empty()) l[i] = ad[i][0];
for (int j = 1; j < ad[i].size(); j++){
assert(ad[i][j] != p);
r[ad[i][j-1]] = ad[i][j];
}
for (int j: ad[i]) {
dfs(j, i, dfs);
}
pr[i] = p;
};
dfs(1, -1, dfs);
for (int i = 1; i <= N; i++){
// if (!l[i]) l[i] = pr[pr[i]], setHint(i, 21, 1);
if (!r[i]) r[i] = pr[pr[i]], setHint(i, 20, 1);
for (int b = 1; b <= 9; b++){
setHint(i, b, (l[i] & (1 << b)));
}
for (int b = 0; b <= 9; b++){
setHint(i, b + 10, (r[i] & (1 << b)));
}
// cout << i << " " << l[i] << " " << r[i] << " " << pr[i] << "\n";
// if (l[i]) cout << i << " " << l[i] << "\n";
// if (r[i]) cout << i << " " << r[i] << "\n";
}
}
}
void speedrun(int subtask, int N, int start) { /* your solution here */
if (subtask == 1 || N <= 4) {
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) {
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));
}
if (v1 && v1 != p) {
goTo(v1);
dfs(v1, u, dfs);
goTo(u);
}
if (v2 && v2 != p) {
goTo(v2);
dfs(v2, u, dfs);
goTo(u);
}
};
dfs(start, -1, dfs);
}
if (subtask == 4) {
auto dfs = [&] (int u, int p = -1, auto&& dfs) -> void {
for (int i = 1; i <= 251; i++){
if (getHint(i)) {
for (int j = (i - 1) * 4; j < i * 4 && j <= N; j++) {
if (j == p || !j) continue;
if (goTo(j)) {
dfs(j, u, dfs);
goTo(u);
}
}
}
}
};
dfs(start, -1, dfs);
}
if (subtask == 5) {
srand(time(NULL));
int mp [maxn] = {};
int vis [maxn] = {};
auto dfs = [&] (int u, int p = 0, auto&& dfs) -> void {
int l = 0, r = 0;
for (int i = 0; i <= 8; i++){
l+=((1 << (i + 1)) * getHint(i + 1));
}
for (int i = 0; i <= 9; i++){
r+=((1 << i) * getHint(i + 10));
}
l^=(rand() % 2);
if (mp[u]) {
l = mp[u];
}
// cout << u << " " << l << " " << r << "\n";
if (l != 0 && l != r && l != p && l <= N && goTo(l)) {
vis[l] = 1;
goTo(l);
dfs(l, u, dfs);
goTo(u);
mp[u] = l;
}
else {
l^=1;
if (l != 0 && l != r && l != p && l <= N && goTo(l)) {
vis[l] = 1;
goTo(l);
dfs(l, u, dfs);
goTo(u);
mp[u] = l;
}
}
// return;
if (r != 0 && !getHint(20) && p) {
vis[r] = 1;
goTo(p);
goTo(r);
dfs(r, p, dfs);
goTo(p);
goTo(u);
}
};
int p = 0;
int s = start;
while (s != 1) {
int r = 0;
for (int i = 0; i <= 9; i++){
r+=((1 << i) * (getHint(i + 10)));
}
if (!p) {
dfs(s, 0, dfs);
for (int i = 1; i <= N; i++){
if (vis[i] || i == s || i == r) continue;
if (goTo(i)) {
p = i;
goTo(s);
}
}
}
// cout << s << " " << r << " " << p << "\n";
if (getHint(20)) {
goTo(p);
s = p;
p = r;
}
else {
goTo(p);
goTo(r);
s = r;
}
}
dfs(s, -1, dfs);
}
}
