#include <bits/stdc++.h>
#include "highway.h"
using namespace std;
#define pb push_back
#define ss second
#define ff first
#define sz(a) int(a.size())
#define all(a) a.begin(),a.end()
typedef long double ld;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
const ll inf = 1e18;
const int mod = 1e9+7; //998244353;
const int maxn = 1e5+5;
const int Xg[4] = {1,0,-1,0}, Yg[4] = {0,1,0,-1};
ll modpw(ll a,ll e) {if(e==0)return 1;ll x=modpw(a*a%mod,e>>1);return e&1?x*a%mod:x;}
int M;
ll init;
int dis[maxn],L[maxn],par[maxn];
vector<pii> adj[maxn],E[maxn],v;
queue<int>q;
vi col;
void bfs(int nd){
q.push(nd);
while(!q.empty()){
int x=q.front(); q.pop();
for(auto i : adj[x]){
if(dis[i.ff] > dis[x]+1){
dis[i.ff]=dis[x]+1;
q.push(i.ff);
E[x].pb({i.ff,i.ss});
E[i.ff].pb({x,i.ss});
}
}
}
}
void dfs(int nd,int pr){
L[nd]=L[pr]+1;
v.pb({L[nd],nd});
for(auto i : E[nd]){
if(i.ff != pr){
par[i.ff]=i.ss;
dfs(i.ff,nd);
}
}
}
int bin(){
int l=0,r=sz(v)-1,md;
while(l <= r){
md=(l+r)/2;
// cout<<md<<'\n';
for(int i = 0;i < M;i++) col[i]=0;
for(int i = md;i <= r;i++) col[par[v[i].ss]]=1;
// cout<<ask(col)<<'\n';
// break;
if(ask(col) > init) l=md+1;
else r=md-1;
}
return l-1;
}
void find_pair(int N, vi U, vi V, int A, int B) {
M = sz(U); col.resize(M);
for(int i = 0;i < M;i++){
adj[U[i]].pb({V[i],i});
adj[V[i]].pb({U[i],i});
}
init = ask(col);
int l = 0,r = M-1,md;
while(l < r){
md = (l+r)/2;
for(int i = 0;i < M;i++) col[i]=0;
for(int i=l;i<=md;i++) col[i] = 1;
if(ask(col) > init) r=md;
else l=md+1;
}
for(int i=0;i<N;i++) dis[i]=mod;
dis[U[r]]=0;
bfs(U[r]);
dfs(V[r],U[r]);
sort(all(v));
int ans = v[bin()].ss;
v.clear(); memset(L,0,sizeof(L));
dfs(U[r],V[r]);
sort(all(v));
// for(auto i : v) cout<<i.ff<<' '<<i.ss<<'\n';
int ans1=v[bin()].ss;
// cout<<ans<<' '<<ans1<<'\n';
answer(ans,ans1);
}
