/*
Say hello to my algoeithmic goose
░░░░░░▄▀▀▀▄░░░░░░░░░░░░░░░░░░░░
░▄███▀░◐░░░▌░░░░░░░░░░░░░░░░░
░░░░░▌░swap░▐░░░░░░░░░░░░░░░░░░
░░░░░▐░HEAP░▐░░░░░░░░░░░░░░░░░░
░░░░░▌░TREE░▐▄▄░░░░░░░░░░░░░░░░
░░░░░▌░pop░▄▀▒▒▀▀▀▀▄░░░░░░░░░░░
░░░░▐░top░▐▒▒push()▒▀▀▄░░░░░░░░
░░░░▐░fib░▐▄▒sift_down()▒▀▄░░░░
░░░░░▀▄░░░░▀▄bin_search()▀▄░░░
░░░░░░░▀▄▄▄▄▄█▄▄▄▄▄▄▄▄▄▀▄░░░░░
░░░░░░░░░░░░▌▌▌▌░░░░░░░░░░░░░░
░░░░░░░░░░░▌▌░▌▌░░░░░░░░░░░░░░░
░░░░░░░░░░▄▄▌▌▄▌▌░░░░░░░░░░░░░
*/
#include "highway.h"
#include <bits/stdc++.h>
#ifndef EVAL
#include "grader.cpp"
#endif
using namespace std;
#define pb push_back
#define sz(x) (int)x.size()
#define ff first
#define ss second
#define vv vector
typedef pair<int, int> pii;
#define ll long long
const int NN = 1e6+5;
vv<pii> edges[NN];
vv<pii> gg[NN];
vv<int> tr;
vv<int> tt;
int un[NN], used[NN], wh[NN], rr, dd[NN], on[NN], l, r;
ll dis;
void dfs(int u, int p, int d = 0){
if(d == dis) tt.pb(u);
dd[u] = d;
for(auto x : edges[u]){
if(x.ff == p) continue;
on[x.ff] = x.ss;
dfs(x.ff, u, d+1);
}
}
void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
//~ cout<<"\n";
for(int i=0;i<sz(V);i++){
gg[V[i]].pb({U[i], i});
gg[U[i]].pb({V[i], i});
}
int mm = sz(V);
tr.resize(mm, 0);
dis = ask(tr)/A;
l = 0, r = mm-1;
while(l+1 < r){
//~ cout<<l<<" "<<r<<"\n";
int m = (l + r+1)>>1;
for(int i=l;i<=m;i++) tr[i] = 1;
ll res = ask(tr);
for(int i=l;i<=m;i++) tr[i] = 0;
if(res > dis*A) r = m;
else l = m+1;
}
tr[r] = 1;
ll res = ask(tr);
if(res > dis*A) l = r;
tr[r] = 0;
rr = V[l];
queue<int> q;
q.push(rr);
used[rr] = 1;
//~ cout<<rr<<"\n";
while(!q.empty()){
int cur = q.front(); q.pop();
for(auto x : gg[cur]){
if(used[x.ff]) continue;
edges[cur].pb(x);
edges[x.ff].pb({cur, x.ss});
used[x.ff] = 1;
q.push(x.ff);
}
}
//~ cout<<"\n";
//~ for(int i=0;i<N;i++){
//~ for(auto x:edges[i]) cout<<i<<" "<<x.ff<<"\n";
//~ }
//~ cout<<"\n";
queue<int> qq;
qq.push(rr);
memset(used, 0, sizeof used);
un[rr] = 1, used[rr] = 1;
int last = rr;
wh[last] = 0;
while(!qq.empty()){
int cur = qq.front(); qq.pop();
for(auto x : edges[cur]){
if(used[x.ff]) continue;
un[x.ff] = ++last;
used[x.ff] = 1;
wh[last] = x.ff;
qq.push(x.ff);
}
}
//~ for(int i=0;i<N;i++) cout<<un[i]<<" ";
//~ cout<<"\n";
l = 1, r = last;
ll br = dis * B;
while(l+1 < r){
int m = (l + r)>>1;
for(int i=1;i<=m;i++){
for(auto x:edges[wh[i]]){
if(un[x.ff] > m) continue;
tr[x.ss] = 1;
}
}
ll res = ask(tr);
tr.assign(mm, 0);
if(res < br) l = m+1;
else r = m;
}
int m = l;
for(int i=1;i<=m;i++){
for(auto x:edges[wh[i]]){
if(un[x.ff] > m) continue;
tr[x.ss] = 1;
}
}
res = ask(tr);
tr.assign(mm, 0);
if(res < br) l = r;
rr = wh[l];
//~ cout<<rr<<"\n";
dfs(rr, -1, 0);
l = 0, r = sz(tt)-1;
while(l < r){
int m = (l + r)>>1;
tr.assign(mm, 0);
for(int i=0;i<=m;i++) tr[on[tt[i]]] = 1;
ll res = ask(tr);
if(res > dis*A) r = m;
else l = m+1;
}
//~ cout<<"\n"<<rr<<" "<<tt[l]<<"\n";
answer(rr, tt[l]);
}
/*
7 6 1 2 0 4
0 1
0 2
0 3
3 4
2 6
3 5
8 10 1 2 1 5
0 1
0 2
1 3
2 3
2 4
3 5
4 5
6 7
7 2
6 4
11 16 1 2 3 8
0 1
1 2
0 3
1 4
1 5
2 6
2 7
7 8
3 4
4 5
5 6
6 7
5 9
9 10
10 6
10 7
*/
