#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;
init(j, i);
sz[i] += sz[j];
}
// cout << i << " " << sz[i] <<"*\n";
}
vector<ll> comp;
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){
v[i.first].push_back(i.second);
v[i.second].push_back(i.first);
}
init(1, 1);
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((n - sz[i]) * 2 > n) ck = 0;
// , cout << j << " -\n";
} else {
if(sz[j] * 2 > n) ck = 0;
// , cout << j << "- \n" ;
}
}
if(ck == 0) continue;
mk[i] = 1;
if(root == 0) root = i;
else r2 = i;
}
assert(root > 0);
// cout << root << " " << r2 << "\n";
init(root, root);
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){
// cout << "? " << i << endl;
// ll t; cin >> t;
// return t;
//}
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){
v[i.first].push_back(i.second);
v[i.second].push_back(i.first);
}
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((n - sz[i]) * 2 > n) ck = 0;
// , cout << j << " -\n";
} else {
if(sz[j] * 2 > n) ck = 0;
// , cout << j << "- \n" ;
}
}
if(ck == 0) continue;
mk[i] = 1;
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;
if(sf == root){
if(t == 1 && visit(r2)){
sf = r2;
vis[sf] = 1;
t = 1;
} else if(t == 1) {
visit(root);
}
}
while(t == 0 && sf != root){
t = visit(pa[sf]);
sf = pa[sf];
vis[sf] = 1;
}
// cout << "s1" << endl;
if(sf == root && t == 0){
t = visit(r2);
sf = r2;
vis[sf] = 1;
}
// cout << "s2" << endl;
// for(int i = 1; i <= n; ++i) cout << pa[i] << " "; cout << "\n";
while(true){
ll ck = 1;
for(auto i : v[sf]){
if(vis[i] || i == pa[sf]) continue;
t = visit(i);
vis[i] = 1;
if(t == 0){
t = visit(sf);
} else {
sf = i;
ck = 0;
break;
}
}
// cout << "done" << endl;
if(ck == 0) continue;
// cout << "! " << sf << "\n";
return;
}
}
//void solve(){
//// vector<ll> ans = mark({{1, 2}, {2, 3}, {3, 4}}, 2);
//// for(auto i : ans) cout << i << " ";
// locate({{1, 2}, {2, 3}, {3, 4}}, 2, 1);
// 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();
//}
