#include "speedrun.h"
#include<bits/stdc++.h>
using namespace std;
namespace sub1{
void init(int n, int a[], int b[]){
setHintLen(n);
for(int i = 1; i < n; i++){
setHint(a[i], b[i], 1);
setHint(b[i], a[i], 1);
}
}
void solve(int n, int start){
function<void(int, int)>dfs;
dfs = [&] (int s, int p){
for(int i = 1; i <= n; i++){
if(i != p && getHint(i)){
goTo(i);
dfs(i, s);
goTo(s);
}
}
};
dfs(start, -1);
}
}
namespace sub2{
void init(int n, int a[], int b[]){
vector<vector<int>>g(n + 1);
for(int i = 1; i < n; i++){
g[a[i]].push_back(b[i]);
g[b[i]].push_back(a[i]);
}
setHintLen(10);
for(int i = 1; i <= n; i++){
if(g[i].size() == 1){
int x = g[i][0];
for(int j = 0; j < 10; j++){
setHint(i, j + 1, x >> j & 1);
}
}
}
}
void solve(int n, int start){
function<void(int, int)>dfs;
dfs = [&] (int s, int p){
int d = 0;
for(int i = 0; i < 10; i++){
if(getHint(i + 1)){
d |= 1 << i;
}
}
if(d == 0){
for(int i = 1; i <= n; i++){
if(i != s && i != p){
goTo(i);
dfs(i, s);
goTo(s);
}
}
}
else if(d != p){
goTo(d);
dfs(d, s);
goTo(s);
}
};
dfs(start, -1);
}
}
namespace sub3{
void init(int n, int a[], int b[]){
vector<vector<int>>g(n + 1);
for(int i = 1; i < n; i++){
g[a[i]].push_back(b[i]);
g[b[i]].push_back(a[i]);
}
setHintLen(20);
for(int i = 1; i <= n; i++){
if(g[i].size() == 1){
g[i].push_back(0);
}
for(int j = 0; j < 2; j++){
for(int k = 0; k < 10; k++){
setHint(i, j * 10 + k + 1, g[i][j] >> k & 1);
}
}
}
}
void solve(int n, int start){
function<void(int, int)>dfs;
dfs = [&] (int s, int p){
for(int i = 0; i < 2; i++){
int d = 0;
for(int j = 0; j < 10; j++){
if(getHint(i * 10 + j + 1)){
d |= 1 << j;
}
}
if(d > 0 && d != p){
goTo(d);
dfs(d, s);
goTo(s);
}
}
};
dfs(start, -1);
}
}
namespace sub45{
void init(int n, int a[], int b[]){
}
void solve(int n, int start){
}
}
void assignHints(int subtask, int n, int a[], int b[]){
if(subtask == 1 || n <= 20){
sub1::init(n, a, b);
}
else if(subtask == 2){
sub2::init(n, a, b);
}
else if(subtask == 3){
sub3::init(n, a, b);
}
else{
sub45::init(n, a, b);
}
}
void speedrun(int subtask, int n, int start){
if(subtask == 1 || n <= 20){
sub1::solve(n, start);
}
else if(subtask == 2){
sub2::solve(n, start);
}
else if(subtask == 3){
sub3::solve(n, start);
}
else{
sub45::solve(n, start);
}
}
