#include<bits/stdc++.h>
#include "highway.h"
using namespace std;
int n, m;
vector<int> u, v;
vector<int> gr[90009];
vector<int> sp;
vector<int> vpr;
int par[90009], pos[90009];
bool used[90009];
void dfs1(int v)
{
used[v]=1;
int brs=gr[v].size();
for(int i=0; i<brs; i++)
{
int nv=gr[v][i];
if(used[nv]) continue;
par[nv]=v;
dfs1(nv);
}
sp.push_back(v);
}
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B)
{
n=N;
u=U;
v=V;
int m = U.size();
for(int i=0; i<m; i++)
{
gr[u[i]].push_back(v[i]);
gr[v[i]].push_back(u[i]);
}
dfs1(0);
vpr.resize(m);
for(int i=0; i<m; i++) vpr[i]=0;
///cout<<1<<endl;
long long expcost=ask(vpr);
for(int i=0; i<m; i++)
{
if(par[u[i]]==v[i]) pos[u[i]]=i;
else if(par[v[i]]==u[i]) pos[v[i]]=i;
}
int le=0, ri=n-2;
///cout<<1<<endl;
while(le<ri)
{
int mid=(le+ri)/2;
for(int i=0; i<m; i++) vpr[i]=0;
for(int j=le; j<=mid; j++) vpr[pos[sp[j]]]=1;
if(ask(vpr)!=expcost) ri=mid;
else le=mid+1;
}
///cout<<sp[le]<<endl;
int v1=sp[le];
sp.resize(0);
for(int i=0; i<n; i++) par[i]=pos[i]=used[i]=0;
vpr.resize(0);
dfs1(v1);
vpr.resize(m);
for(int i=0; i<m; i++) vpr[i]=0;
///cout<<1<<endl;
expcost=ask(vpr);
for(int i=0; i<m; i++)
{
if(par[u[i]]==v[i]) pos[u[i]]=i;
else if(par[v[i]]==u[i]) pos[v[i]]=i;
}
le=0, ri=n-2;
while(le<ri)
{
int mid=(le+ri)/2;
for(int i=0; i<m; i++) vpr[i]=0;
for(int j=le; j<=mid; j++) vpr[pos[sp[j]]]=1;
if(ask(vpr)!=expcost) ri=mid;
else le=mid+1;
}
answer(v1, sp[le]);
}
