#include "incursion.h"
#include<bits/stdc++.h>
using namespace std;
typedef int ll;
const int mn = 45005;
ll n, sz[mn], mk[mn], pa[mn], vis[mn];
vector<ll> v[mn];
void init(ll i, ll p){
sz[i] = 1;
pa[i] = p;
for(auto j : v[i]){
if(j == p) continue;
sz[i] += sz[j];
}
}
vector<ll> comp;
ll ps(ll i){
return lower_bound(comp.begin(), comp.end(), i) - comp.begin() + 1;
}
vector<ll> mark(vector<pair<ll, ll> > edge, ll sf){
for(auto i : edge) comp.push_back(i.first), comp.push_back(i.second);
sort(comp.begin(), comp.end());
comp.erase(unique(comp.begin(), comp.end()), comp.end());
ll n = comp.size();
for(auto &i : edge) i.first = ps(i.first), i.second = ps(i.second);
init(1, 0);
ll root = 0, r2 = 0;
for(int i = 1; i <= n; ++i){
ll ck = 1;
for(auto j : v[i]){
if(j == pa[i]){
if(sz[j] - sz[i] >= n / 2) ck = 0;
} else {
if(sz[j] >= n / 2) ck = 0;
}
}
if(ck == 0) continue;
mk[i] = 1;
if(root == 0) root = i;
else r2 = i;
}
init(root, 0);
vector<ll> ans;
ans.assign(n, 0);
while(sf != root) ans[sf - 1] = 1, sf = pa[sf];
ans[root - 1] = 1;
return ans;
}
bool cmp(ll a, ll b){
return sz[a] > sz[b];
}
//int visit(ll i){
// return i;
//}
void locate(vector<pair<ll, ll> > edge, ll sf, ll t){
for(auto i : edge) comp.push_back(i.first), comp.push_back(i.second);
sort(comp.begin(), comp.end());
comp.erase(unique(comp.begin(), comp.end()), comp.end());
ll n = comp.size();
for(auto &i : edge) i.first = ps(i.first), i.second = ps(i.second);
init(1, 0);
ll root = 0, r2 = 0;
for(int i = 1; i <= n; ++i){
ll ck = 1;
for(auto j : v[i]){
if(j == pa[i]){
if(sz[j] - sz[i] >= n / 2) ck = 0;
} else {
if(sz[j] >= n / 2) ck = 0;
}
}
if(ck == 0) continue;
mk[i] = ck;
if(root == 0) root = i;
else r2 = i;
}
init(root, 0);
for(int i = 1; i <= n; ++i){
sort(v[i].begin(), v[i].end(), cmp);
}
vis[sf] = 1;
while(t > 0 && sf != root){
t = visit(pa[sf]);
sf = pa[sf];
vis[sf] = 1;
}
if(sf == root && t > 0){
t = visit(r2);
sf = r2;
vis[sf] = 1;
}
while(true){
ll ck = 1;
for(auto i : v[sf]){
if(vis[i]) continue;
t = visit(i);
vis[i] = 1;
if(t == 1){
t = visit(sf);
} else {
sf = i;
ck = 0;
break;
}
}
if(ck == 0) continue;
return;
}
}
//void solve(){
// return;
//}
//
//int main(){
// ios_base::sync_with_stdio(false);
// cin.tie(NULL);
// if(fopen(".INP", "r")) {
// freopen(".INP", "r", stdin);
// freopen(".OUT", "w", stdout);
// }
// int testCase = 1;
// //cin >> testCase;
// while(testCase--) solve();
//}
