#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;
const int NN = 1e5+5;
vv<pii> edges[NN];
vv<int> tr, tt;
int un[NN], used[NN], wh[NN], dis, rr, dd[NN];
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;
dfs(x.ff, u, d+1);
}
}
void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
for(int i=0;i<sz(V);i++){
edges[V[i]].pb({U[i], i});
edges[U[i]].pb({V[i], i});
}
int mm = sz(V);
tr.resize(mm, 0);
int ans = ask(tr);
dis = ans/A;
queue<int> qq;
qq.push(0);
un[0] = 1, used[0] = 1;
int last = 1;
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);
}
}
int l = 1, r = last;
int br = dis * B;
while(l < r){
int m = (l + r)>>1;
for(int i=l;i<=m;i++){
for(auto x:edges[wh[i]]){
if(un[x.ff] > m || un[x.ff] < l) continue;
tr[x.ss] = 1;
}
}
int res = ask(tr);
tr.assign(mm, 0);
if(res == br) r = m;
else l = m+1;
}
tr.assign(mm, 0);
rr = wh[l];
dfs(rr, -1, 0);
l = 0, r = sz(tt)-1;
while(l < r){
int m = (l + r)>>1;
for(int i=l;i<=m;i++){
for(auto x:edges[tt[i]]) if(dd[x.ff] < dd[tt[i]]) tr[x.ss] = 1;
}
int res = ask(tr);
tr.assign(mm, 0);
if(res > dis*A) r = m;
else l = m+1;
}
//cout<<rr<<" "<<tt[l]<<"\n";
answer(rr, tt[l]);
}
/*
7 6 1 2 0 4
0 1
0 4
1 2
1 3
4 5
4 6
*/
