#include <bits/stdc++.h>
#include "incursion.h"
using namespace std;
vector<int> adj[45005];
int n;
int sz[45005],par[45005];
bool cmp(int a, int b){
return sz[a]>sz[b];
}
int dfs(int x, int p){
par[x]=p;
sz[x]=1;
for(int i:adj[x]){
if(i==p) continue;
sz[x]+=dfs(i,x);
}
return sz[x];
}
int findcent(int x, int p){
for(int i:adj[x]){
if(i==p) continue;
if(sz[i]*2>n) return findcent(i,x);
}
return x;
}
vector<int> mark(vector<pair<int,int> > ed, int ans){
n=ed.size()+1;
vector<int> ret(n,1);
for(int i=0; i<=n; i++){
adj[i].clear();
par[i]=-1;
}
for(pair<int,int> i:ed){
adj[i.first].push_back(i.second);
adj[i.second].push_back(i.first);
}
dfs(ans,-1);
int cent=findcent(ans,-1);
while(cent!=-1){
ret[cent-1]=0;
cent=par[cent];
}
return ret;
}
void follow(int cur){
sort(adj[cur].begin(),adj[cur].end(),cmp);
for(int i:adj[cur]){
if(i==par[cur]) continue;
int tst=visit(i);
if(tst) visit(cur);
else{
follow(i);
return;
}
}
return;
}
void locate(vector<pair<int,int> > ed, int cur, int t){
n=ed.size()+1;
vector<int> ret(n,1);
for(int i=0; i<=n; i++){
adj[i].clear();
par[i]=-1;
}
for(pair<int,int> i:ed){
adj[i.first].push_back(i.second);
adj[i.second].push_back(i.first);
}
dfs(cur,-1);
int cent=findcent(cur,-1);
dfs(cent,-1);
while(t==1){
if(cur==cent){
int legit=-1;
for(int i:adj[cent]){
if(sz[i]*2==n) legit=i;
}
assert(legit!=-1);
cent=legit;
dfs(cent,-1);
}
t=visit(par[cur]);
cur=par[cur];
}
follow(cur);
}
