#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[]){
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]);
}
vector<int>order(1, -1), par(n + 1, 0);
function<void(int)>dfs;
dfs = [&] (int s){
order.push_back(s);
for(int& d : g[s]){
if(d != par[s]){
par[d] = s;
dfs(d);
}
}
};
dfs(1);
setHintLen(20);
for(int i = 1; i < n; i++){
if(par[order[i + 1]] == order[i]){
for(int j = 0; j < 10; j++){
setHint(order[i], j + 1, par[order[i]] >> j & 1);
}
}
else{
for(int j = 0; j < 10; j++){
setHint(order[i], j + 1, par[order[i + 1]] >> j & 1);
}
}
for(int j = 0; j < 10; j++){
setHint(order[i], j + 11, order[i + 1] >> j & 1);
}
}
}
void solve(int n, int start){
auto get = [&] (int jump){
int ans = 0;
for(int i = 0; i < 10; i++){
if(getHint(jump * 10 + i + 1)){
ans |= 1 << i;
}
}
return ans;
};
int s_par = get(0);
if(s_par != 0){
if(goTo(s_par)){
start = s_par;
}
else{
for(int i = 1; i <= n; i++){
if(i != start && goTo(i)){
start = i;
break;
}
}
}
}
else if(get(1) == 0){
for(int i = 1; i <= n; i++){
if(i != start && goTo(i)){
start = i;
break;
}
}
}
while(start != 1){
goTo(start = get(0));
}
vector<int>par(n + 1);
for(int i = 1; i < n; i++){
int nxt_ver = get(1);
if(goTo(nxt_ver)){
par[nxt_ver] = start;
start = nxt_ver;
}
else{
int need = get(0);
while(start != need){
goTo(start = par[start]);
}
goTo(start = nxt_ver);
}
}
}
}
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);
}
}
