#include "highway.h"
#include "bits/stdc++.h"
using namespace std;
#define ll long long
int const MAXN=1e5+10;
vector<pair<int,int>>nei[MAXN];
vector<int>ver[MAXN]={};
int h[MAXN],P[MAXN],ind[MAXN];
void dfs(int u,int p=-1)
{
// cout<<u<<' '<<p<<endl;
P[u]=p;
ver[h[u]].push_back(u);
for (auto [v,i]:nei[u])
{
if (v==p)
{
ind[u]=i;continue;
}
h[v]=h[u]+1;
dfs(v,u);
}
}
void find_pair(int N, vector<int> U, vector<int> V, int A, int B)
{
int M=U.size();
for (int i=0;i<M;i++)
{
nei[U[i]].push_back({V[i],i});
nei[V[i]].push_back({U[i],i});
}
h[1]=0;
P[1]=-1;
dfs(1);
vector<int>w;
for (int i=0;i<M;i++)
w.push_back(0);
ll mn=ask(w);
ll dis=mn/A;
int mx=0;
while (ver[mx].size())
mx++;
mx--;
int st=0,en=mx+1;
while (st+1<en)
{
for (int i=0;i<M;i++)
w[i]=0;
int mid=(st+en)/2;
for (int i=mid;i<=mx;i++)
{
for (auto j:ver[i])
w[ind[j]]=1;
}
ll cur=ask(w);
if (cur!=mn)
st=mid;
else
en=mid;
}
int dh=st;
int sz=ver[st].size();
st=-1,en=sz-1;
while (st+1<en)
{
int mid=(st+en)/2;
for (int i=0;i<M;i++)
w[i]=0;
for (int j=0;j<=mid;j++)
w[ind[ver[dh][j]]]=1;
ll cur=ask(w);
if (cur!=mn)
en=mid;
else
st=mid;
}
int s=ver[dh][en];
int t;
st=-1,en=mx;
while (st+1<en)
{
for (int i=0;i<M;i++)
w[i]=0;
int mid=(st+en)/2;
for (int i=0;i<=mid;i++)
{
for (auto j:ver[i])
w[ind[j]]=1;
}
ll cur=ask(w);
if (cur!=mn)
en=mid;
else
st=mid;
}
int lch=st;
int ud=lch+dis-(dh-lch);
if (ud==lch)
{
t=s;
while (h[t]!=ud)
t=P[t];
answer(s,t);
return;
}
int sm=0;
{
if (ud>dh)
{
answer(0,0);
return;
}
int sz=ver[ud].size();
int st=0,en=sz;
while (st+1<en)
{
for (int i=0;i<M;i++)
w[i]=0;
int mid=(st+en)/2;
for (int i=mid;i<sz;i++)
w[ind[ver[ud][i]]]=1;
ll cur=ask(w);
if (cur!=mn)
st=mid;
else
en=mid;
}
sm=ver[ud][st];
st=-1,en=sz-1;
while (st+1<en)
{
for (int i=0;i<M;i++)
w[i]=0;
int mid=(st+en)/2;
for (int i=0;i<=mid;i++)
w[ind[ver[ud][i]]]=1;
ll cur=ask(w);
if (cur!=mn)
en=mid;
else
st=mid;
}
sm+=ver[ud][en];
t=s;
while (h[t]!=ud)
t=P[t];
t=sm-t;
}
answer(s,t);
}
