#include<bits/stdc++.h>
typedef long long ll;
#define pb push_back
#define fr first
#define sc second
#define endl '\n'
using namespace std;
#define mid ((left+right)>>1)
#include"incursion.h"
int n;
int par[45023],sub[45023];
pair<int,int>cent;
vector<int>komsu[45023];
int tur[45023];
void dfs(int pos,int las){
sub[pos]=1;
for(int x:komsu[pos]){
if(x==las)continue;
dfs(x,pos);
sub[pos]+=sub[x];
}
}
void dfs(int pos){
for(int x:komsu[pos]){
if(x==par[pos])continue;
par[x]=pos;
dfs(x);
}
}
vector<int> mark(vector<pair<int,int>>F,int safe){
n=F.size()+1;
for(auto&x:F){
komsu[x.fr].pb(x.sc);
komsu[x.sc].pb(x.fr);
}
dfs(1,1);
cent.fr=1;
while(true){
int nex=-1;
for(int x:komsu[cent.fr]){
if(sub[x]>sub[cent.fr])continue;
if(sub[x]*2>n){
nex=x;
break;
}
if(sub[x]*2==n){
cent.sc=x;
break;
}
}
if(nex==-1)break;
cent.fr=nex;
}
par[cent.fr]=cent.sc;
par[cent.sc]=cent.fr;
dfs(cent.fr);
if(cent.sc)dfs(cent.sc);
vector<int>ans(n);
for(int i=0;i<n;i++){
ans[i]=1;
}
int pos=safe;
while(pos!=cent.fr&&pos!=cent.sc){
ans[pos-1]=0;
pos=par[pos];
}
ans[pos-1]=0;
return ans;
}
void locate(vector<pair<int,int>>F,int curr,int t){
n=F.size()+1;
for(int i=1;i<=n;i++){
komsu[i].clear();
par[i]=0;
cent={0,0};
}
for(auto&x:F){
komsu[x.fr].pb(x.sc);
komsu[x.sc].pb(x.fr);
}
dfs(1,1);
cent.fr=1;
while(true){
int nex=-1;
for(int x:komsu[cent.fr]){
if(sub[x]>sub[cent.fr])continue;
if(sub[x]*2>n){
nex=x;
break;
}
if(sub[x]*2==n){
cent.sc=x;
break;
}
}
if(nex==-1)break;
cent.fr=nex;
}
par[cent.fr]=cent.sc;
par[cent.sc]=cent.fr;
dfs(cent.fr);
if(cent.sc)dfs(cent.sc);
int x=t;
int pos=curr;
for(int i=1;i<=n;i++){
tur[i]=-1;
}
while(x){
tur[pos]=1;
x=visit(par[pos]);
pos=par[pos];
}
tur[pos]=0;
dfs(pos,pos);
while(true){
if(tur[pos]==1){
visit(par[pos]);
pos=par[pos];
continue;
}
int nex=-1;
for(int x:komsu[pos]){
if(tur[x]!=-1)continue;
if(x==par[pos])continue;
if(nex==-1||sub[x]>sub[nex])nex=x;
}
if(nex==-1)return;
tur[nex]=visit(nex);
pos=nex;
}
}
