#include "highway.h"
#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define x first
#define y second
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
vector<pii>g[90015];
vector<int>all[90015];
vector<int>qry;
ll n,m,mx,mn,fa[90015],dep[90015];
void bfs(int root){
for (int i=0;i<=n;i++){
fa[i]=0; dep[i]=0; mx=0;
all[i].clear();
}
queue<int>q; q.push(root);
dep[root]=1; mx=1;
all[1].push_back(root);
while (!q.empty()){
int p=q.front(); q.pop();
for (auto [i,idx]:g[p]){
if (!dep[i]){
dep[i]=dep[p]+1; fa[i]=idx; mx=max(mx,dep[i]);
all[dep[i]].push_back(i);
q.push(i);
}
}
}
}
int solve1(int root){
bfs(root);
int l=2,r=mx+1;
while (l<r){
int mid=(l+r)>>1;
for (auto i:all[mid])
qry[fa[i]]=1;
int dis=ask(qry);
if (dis==mn) r=mid;
else l=mid+1;
for (auto i:all[mid])
qry[fa[i]]=0;
}
l--;
int p=l;
l=0,r=all[p].size();
while (l<r){
int mid=(l+r)>>1;
for (int j=l;j<=mid;j++)
qry[fa[all[p][j]]]=1;
int dis=ask(qry);
for (int j=l;j<=mid;j++)
qry[fa[all[p][j]]]=0;
if (dis!=mn) r=mid;
else l=mid+1;
}
return all[p][l];
}
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
n=N; m=U.size();
for (int i=0;i<m;i++){
g[U[i]].push_back({V[i],i});
g[V[i]].push_back({U[i],i});
}
qry.resize(m,0);
mn=ask(qry);
int s=solve1(0),d=mn/A;
bfs(s);
int p=d+1;
int l=0,r=all[p].size();
while (l<r){
int mid=(l+r)>>1;
for (int j=l;j<=mid;j++)
qry[fa[all[p][j]]]=1;
int dis=ask(qry);
for (int j=l;j<=mid;j++)
qry[fa[all[p][j]]]=0;
if (dis!=mn) r=mid;
else l=mid+1;
}
int t=all[p][l];
answer(s,t);
}
/*
6 5 2 3 1 5
0 1
1 2
2 4
0 3
3 5
*/
