#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define ll long long
#define dl double long
const int maxn = 200100;
int m;
ll dist;
bool used[maxn];
int h[maxn];
int pa[maxn];
vector < int > nnj,f;
vector < pair < int , int > > v[maxn],g[maxn];
void dfs( int x , int p , int id )
{
h[x] = h[p] + 1;
f.push_back(x);
pa[x] = id;
for( auto y : g[x] ){
if( y.fi != p ){
dfs( y.fi , x , y.se );
}
}
}
int solve( int x )
{
f.clear();
h[x] = 0;
dfs( x , x , -1 );
vector < pair < int , int > > v;
for( int i = 0; i < (int)f.size(); i++ ){
v.push_back({ h[f[i]] , f[i] });
}
sort( v.rbegin() , v.rend() );
int l = 0 , r = (int)v.size() - 1;
int res = (int)v.size() - 1;
while( l <= r ){
int mi = (l + r) / 2;
vector < int > w(m , 0);
for( auto y : nnj ){
w[y] = 1;
}
for( int i = 0; i <= mi; i++ ){
if( pa[v[i].se] != -1 ){
w[pa[v[i].se]] = 1;
}
}
ll di = ask( w );
if( di > dist ){
res = min( res , mi );
r = mi - 1;
}else l = mi + 1;
}
return v[res].se;
}
void bfs( int x , int y )
{
vector < int > d(maxn , 1e9);
vector < int > p(maxn , -1);
d[x] = d[y] = 0;
queue < int > q;
q.push(x);
q.push(y);
while( !q.empty() ){
int x = q.front();
q.pop();
for( auto y : v[x] ){
if( d[y.fi] == 1e9 ){
d[y.fi] = d[x] + 1;
used[y.se] = true;
g[x].push_back(y);
g[y.fi].push_back({ x , y.se });
q.push(y.fi);
}
}
}
}
void find_pair(int N, vector<int> U, vector<int> V, int A, int B)
{
m = (int)U.size();
vector < int > a,b;
vector < int > w(m , 0);
dist = ask(w);
for( int i = 0; i < m; i++ ){
int x = U[i] , y = V[i];
v[x].push_back({y , i});
v[y].push_back({x , i});
}
int l = 0 , r = m - 1;
while( l < r ){
int mid = (l + r) / 2;
vector < int > w(m , 0);
for( int j = 0; j <= mid; j++ )w[j] = 1;
ll x = ask( w );
if( x == dist )l = mid + 1;
else r = mid;
}
bfs( U[l] , V[l] );
for( int i = 0; i < m; i++ ){
if( used[i] )continue;
nnj.push_back(i);
}
int ans1 = solve( U[l] );
int ans2 = solve( V[l] );
answer(ans1 , ans2);
}
