#include <bits/stdc++.h>
#include "incursion.h"
using namespace std;
const int N=45001;
/*int visit(int v){
cout<<"? "<<v<<'\n';
int c;
cin>>c;
return c;
}*/
std::vector<int> mark(std::vector<std::pair<int, int>>f, int safe){
queue<pair<int,int>> q;
vector<int> ans;
q.push({safe,0});
vector<vector<int>> g(N);
vector<bool> vis(N,0);
int n=0;
for(int i=0;i<f.size();++i){
g[f[i].first].push_back(f[i].second);
g[f[i].second].push_back(f[i].first);
n=max(n,f[i].first);
n=max(n,f[i].second);
}
ans.resize(n);
vis[1]=1;
while(!q.empty()){
int x=q.front().first;
int y=q.front().second;
ans[x-1]=y;
for(auto j:g[x]){
if(!vis[j]){
q.push({j,y+1});
vis[j]=1;
}
}
q.pop();
}
return ans;
}
vector<vector<int>> g(N);
int sz[N];
void dfs(int v,int p){
int c=0;
sz[v]=1;
vector<pair<int,int>> r;
for(auto i:g[v]){
if(i!=p){
dfs(i,v);
sz[v]+=sz[i];
r.push_back({sz[i],c});
}
++c;
}
sort(r.begin(),r.end());
if(!r.empty())
swap(g[v][r[0].second],g[v][0]);
}
void locate(std::vector<std::pair<int, int>> f, int cur, int t){
if(t==0){
return;
}
for(int i=0;i<f.size();++i){
g[f[i].first].push_back(f[i].second);
}
for(int i=0;i<f.size();++i){
g[f[i].second].push_back(f[i].first);
}
dfs(cur,0);
int nxt;
for(int i=0;i<g[cur].size();++i){
int o=visit(g[cur][i]);
if(o>t){
visit(cur);
}
else{
nxt=g[cur][i];
t=o;
}
}
int pap=cur;
cur=nxt;
while(t!=0){
int nxt;
for(int i=0;i<g[cur].size();++i){
if(g[cur][i]==pap){
continue;
}
int o=visit(g[cur][i]);
if(o>t){
visit(cur);
}
else{
nxt=g[cur][i];
t=o;
}
}
pap=cur;
cur=nxt;
}
}
/*int main(){
vector<int> u=mark({{1,2}, {2,3}},1);
for(int i=0;i<u.size();++i){
cout<<u[i]<<' ';
}
locate({{1,2}, {2,3}},3,2);
return 0;
}*/
