#include "thief.h"
#include <bits/stdc++.h>
using namespace std;
void myassert(bool bl)
{
if(!bl) while(1);
}
int n,m;
vector<int> u, v;
vector<int> arb[10005];
vector<int> myq;
void dfs(int nod, int par, int parid, int semn)
{
myassert(par != -1);
myq[parid] = ((nod == u[parid]) ^ semn);
for(int eid:arb[nod])
{
if(eid == parid)
continue;
int adj = u[eid] + v[eid] - nod;
dfs(adj, nod, eid, semn);
}
}
int cine[15005];
vector<int> ord;
void dfs_ord(int nod, int par)
{
for(int eid:arb[nod])
{
int adj = u[eid] + v[eid] - nod;
if(adj == par)
continue;
cine[eid] = adj;
ord.push_back(eid);
dfs_ord(adj, nod);
}
}
int find_node(int root, int semn, vector<int> good_children)
{
myq.clear();
myq.resize(m, 0);
vector<int> isgood(m, 0);
for(int x:good_children) isgood[x] = 1;
for(int eid:arb[root])
{
int adj = u[eid] + v[eid] - root;
dfs(adj, root, eid, isgood[eid] ^ semn);
}
//myassert(query(myq));
if(!query(myq))
return -1;
ord.clear();
for(int eid:arb[root])
{
int adj = u[eid] + v[eid] - root;
if(isgood[eid])
{
ord.push_back(eid);
cine[eid] = adj;
dfs_ord(adj, root);
}
}
//for(int x:ord) cerr<<x<<" ";cerr<<" ord\n";
int st = -1, dr = ord.size() - 1, ans = -2;
while(st <= dr)
{
int mij = (st + dr) / 2;
vector<int> newq = myq;
for(int i=0;i<ord.size();i++)
{
if(i <= mij)
newq[ord[i]] = myq[ord[i]];
else
newq[ord[i]] = myq[ord[i]] ^ 1;
}
if(query(newq))
{
ans = mij;
dr = mij-1;
}
else
{
st = mij+1;
}
}
myassert(ans != -2);
myassert(ans >= -1);
if(ans == -1)
{
//cerr<<root<<" hmm root\n";
return root;
}
else
{
//cerr<<cine[ord[ans]]<<" hmm other\n";
return cine[ord[ans]];
}
}
bool enter_endgame(int root, vector<int> good_children)
{
//int A = find_node(root, 0, good_children);
vector<bool> isgood(m, 0);
for(int x:good_children)
isgood[x] = 1;
vector<int> other_good;
for(int x:arb[root])
if(!isgood[x])
other_good.push_back(x);
int A = find_node(root, 0, good_children);
int B = find_node(root, 1, other_good);
if(A == root && find_node(root, 0, other_good))
{
A = find_node(root, 0, other_good);
}
if(B == root && find_node(root, 1, good_children))
{
B = find_node(root, 1, good_children);
}
if(A != -1 && B != -1)
{
//cerr<<A<<" "<<B<<" my answer\n";
answer(A, B);
return 1;
}
return 0;
//cerr<<A<<" "<<B<<" my answer\n";
}
bool iss[10005];
int siz[10005];
void get_sizes(int nod, int par)
{
siz[nod] = 1;
for(int eid:arb[nod])
{
int adj = u[eid] + v[eid] - nod;
if(adj == par || iss[adj])
continue;
get_sizes(adj, nod);
siz[nod] += siz[adj];
}
}
int get_centroid(int nod, int par, int tot)
{
for(int eid:arb[nod])
{
int adj = u[eid] + v[eid] - nod;
if(adj == par || iss[adj])
continue;
if(siz[adj]*2 > tot)
return get_centroid(adj, nod, tot);
}
return nod;
}
void solve_abore()
{
vector<vector<int>> cens(10005);
cens[0].push_back(0);
for(int d=0;;d++)
{
if(cens[d].empty())
break;
//cerr<<d<<" d\n";
int maxsiz = 0;
for(int&nod:cens[d])
{
get_sizes(nod, -1);
nod = get_centroid(nod, -1, siz[nod]);
iss[nod] = 1;
int cntc = 0;
for(int eid:arb[nod])
{
int adj = u[eid] + v[eid] - nod;
if(!iss[adj])
{
cens[d+1].push_back(adj);
cntc++;
}
}
maxsiz = max(maxsiz, cntc);
}
//cerr<<"got centroids\n";
//check if nod is one of the special nodes------------------------------
int b = 0;
while((1<<b) < maxsiz)
b++;
for(;b>=0;b--)
{
//cerr<<b<<" start b\n";
vector<int> aux(m, 0);
for(int nod:cens[d])
{
vector<pair<int,int>> chs;
for(int eid:arb[nod])
{
int adj = u[eid] + v[eid] - nod;
if(!iss[adj])
chs.push_back({adj, eid});
}
for(int poz=0;poz<chs.size();poz++)
{
if((1<<b)&poz)
{
aux[chs[poz].second] = (nod == u[chs[poz].second]);
}
else
{
aux[chs[poz].second] = (nod != u[chs[poz].second]);
}
}
}
vector<int> q[2];
for(int i=0;i<m;i++)
{
q[0].push_back(aux[i]);
q[1].push_back(aux[i] ^ 1);
}
for(int semn=0;semn<2;semn++)
{
if(query(q[semn]))
{
//do a binary search to find what node this is about and then enter endgame
//cerr<<"started binsearch\n";
int st = 0, dr = cens[d].size() - 1, ans = -1;
while(st <= dr)
{
int mij = (st + dr) / 2;
vector<int> newq = q[semn];
for(int i=0;i<cens[d].size();i++)
{
int nod = cens[d][i];
if(i <= mij)
{
for(int eid:arb[nod])
if(!iss[u[eid] + v[eid] - nod])
newq[eid] = q[semn][eid];
}
else
{
for(int eid:arb[nod])
if(!iss[u[eid] + v[eid] - nod])
newq[eid] = (q[semn][eid] ^ 1);
}
}
if(query(newq))
{
ans = mij;
dr = mij-1;
}
else
{
st = mij+1;
}
}
assert(ans != -1);
//cerr<<"ended binsearch\n";
int root = cens[d][ans];
vector<int> good_children;
int poz = 0;
for(int eid:arb[root])
{
int adj = u[eid] + v[eid] - root;
if(!iss[adj])
{
if((((1<<b)&poz) == 0) == semn)
{
good_children.push_back(eid);
}
poz++;
}
}
//cerr<<"got to endgame\n";
enter_endgame(root, good_children);
return;
}
}
}
}
}
void solve(int N, int M, std::vector<int> U, std::vector<int> V)
{
myassert(M == N-1);
n = N;
m = M;
u = U;
v = V;
for(int i=0;i<m;i++)
{
arb[u[i]].push_back(i);
arb[v[i]].push_back(i);
}
//solve_abore();//------------------------------------------------------------------
for(int i=0;i<n;i++)
{
for(int lim=0;lim<arb[i].size();lim++)
{
vector<int> c0, c1;
for(int poz=0;poz<arb[i].size();poz++)
{
if(poz <= lim)
c0.push_back(arb[i][poz]);
else
c1.push_back(arb[i][poz]);
}
if(enter_endgame(i, c0))
return;
if(enter_endgame(i, c1))
return;
}
}
assert(0);
}
/*
5 4 3 0
0 1
1 2
2 3
3 4
5 4 0 4
0 1
0 3
1 2
1 4
*/
