#include <bits/stdc++.h>
#define vi vector<int>
#define gi greater<int>
#define gr greater
#define ve vector
#define ll long long
#define vf vector<float>
#define vll vector<pair<ll,ll>>
#define ii pair<int,int>
#define pll pair<ll,ll>
#define vvi vector<vi>
#define vii vector<ii>
#define gii greater<ii>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define INF 1e9
#define eps 1e-7
#define eps1 1e-2
#define optimise ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define MAX_A 2e5+5
using namespace std;
const int MOD = 1e9+7;
const int nax = 1e5+5;
typedef complex<int> Point;
#define X real()
#define Y imag()
#include "highway.h"
vii adj[nax];
vi w;
int mxd= 0, dep[nax],m,nb;
ii par[nax];
void dfs(int u, int p){
for(auto x : adj[u]){
if(x.fi == p) continue;
dep[x.fi] = dep[u]+1;
par[x.fi] = {u,x.se};
mxd = max(mxd, dep[x.fi]);
dfs(x.fi,u);
}
}
void color(int u, int p,int cl){
for(auto x : adj[u]){
if(x.fi == p) continue;
w[x.se] = cl;
color(x.fi, u, cl);
}
}
void sub(int root){
dep[root] = 0;
par[root] = {root,root};
dfs(root,root);
vvi sm(mxd+1);
w.clear();
w.assign(m,0);
for (int i = 0; i < nb; ++i)
{
sm[dep[i]].pb(i);
}
int totl = ask(w);
int l = 0, r = mxd+1;
while(l < r){
w.clear();
w.assign(m,0);
int md = (l+r)/2;
for(auto x : sm[md]){
color(x,par[x].fi,1);
}
int qr = ask(w);
if(qr == totl){
r = md;
} else {
l = md+1;
}
}
int dpanc = r;
if(r == 0){
answer(root,root);
return;
}
l = 0, r = sm[dpanc].size();
while(l< r){
w.clear();
w.assign(m,0);
int md = (l+r)/2;
for (int i = l; i <= md; ++i)
{
int u = sm[dpanc][i];
w[par[u].se] = 1;
}
int qr = ask(w);
if(qr==totl){
l = md+1;
} else {
r = md;
}
}
answer(root, sm[dpanc][r]);
}
void find_pair(int n, vi u, vi v, int a, int b) {
m = u.size(), nb = n;
for (int i = 0; i < m; ++i)
{
adj[u[i]].pb({v[i],i});
adj[v[i]].pb({u[i],i});
}
dep[0] = 0;
par[0] = {0,0};
dfs(0,0);
vvi sm(mxd+1);
w.assign(m,0);
for (int i = 0; i < n; ++i)
{
sm[dep[i]].pb(i);
}
int totl = ask(w);
int l = 0, r = mxd+1;
while(l < r){
w.clear();
w.assign(m,0);
int md = (l+r)/2;
for(auto x : sm[md]){
color(x,par[x].fi,1);
}
int qr = ask(w);
if(qr == totl){
r = md;
} else {
l = md+1;
}
}
int mxd = r;
if(r == 0){
answer(0,0);
return;
}
l = 0, r = sm[mxd].size();
while(l< r){
w.clear();
w.assign(m,0);
int md = (l+r)/2;
for (int i = l; i <= md; ++i)
{
int u = sm[mxd][i];
w[par[u].se] = 1;
}
int qr = ask(w);
if(qr==totl){
l = md+1;
} else {
r = md;
}
}
sub(sm[mxd][r]);
}
