#include "highway.h"
#include <bits/stdc++.h>
#define int long long
#define all(a) a.begin(), a.end()
#define rep(i,n) for(int i = 0; i<n; i++)
using namespace std;
int k,m;
struct edge
{
int w, i;
};
int N=90000, c=0;
vector<vector<edge>>E;
vector<int>p(N);
vector<int>ped(N,-1);
vector<int>pre(N,-1);
vector<int>post(N,-1);
vector<int>dep(N,0);
vector<vector<int>>up(N,vector<int>(18,0));
vector<int> dfs(int v, int par)
{
if(par==-1) up[v][0]=v;
p[v]=par;
pre[v]=c++;
vector<int>cr;
if(E[v].size()==1) cr.push_back(v);
for(auto [w,i] : E[v]) if(w!=par)
{
dep[w]=dep[v]+1;
vector<int> ans = dfs(w,v);
ped[w]=i;
if(ans.size()>cr.size()) swap(cr,ans);
for(int x : ans) cr.push_back(x);
up[w][0]=v;
}
post[v]=c++;
return cr;
}
void act(int to, int v, int c, int lim, vector<signed>&w)
{
if(v==to||ped[v]==-1||w[ped[v]]||c==lim) return;
w[ped[v]]=true;
act(to,p[v],c+1, lim, w);
}
bool ischild(int w, int v)
{
return pre[w]>=pre[v]&&post[w]<=post[v];
}
int lca(int a, int b)
{
if(a==b) return a;
if(dep[a]<dep[b]) swap(a,b);
for(int j = 17; j >=0; j--) if(!ischild(b,up[a][j])) a=up[a][j];
return up[a][0];
}
void findr(int v, int A, int B)
{
vector<int>leaves=dfs(v,-1);
for(int j = 1; j < 18; j++) rep(i,E.size()) up[i][j]=up[up[i][j-1]][j-1];
int start = 0, end = leaves.size();
while (end-start>1)
{
vector<signed>w(m,0);
int cur = (start+end)/2;
for(int i = cur; i < leaves.size(); i++)
{
act(v,leaves[i],0,1e8,w);
}
if(k*B==ask(w)) start=cur;
else end=cur;
}
int v1=leaves[start];
start = 0, end = leaves.size();
while (end-start>1)
{
vector<signed>w(m,0);
int cur = (start+end)/2;
for(int i = cur; i>=0; i--)
{
act(v,leaves[i],0,1e8,w);
}
if(k*B==ask(w)) end=cur;
else start=cur;
}
int v2=leaves[end];
int deplca=dep[lca(v1,v2)];
int lca1 = lca(v2,v1);
if(v1!=v2)
{
for(int j = 17; j >= 0; j--)
{
if(dep[up[v1][j]]<deplca) continue;
vector<signed>w(m,0);
act(v, up[v1][j],0,1e8,w);
act(v, v2,0,1e8,w);
if(ask(w)==k*B) v1=up[v1][j];
}
for(int j = 17; j >= 0; j--)
{
if(dep[up[v2][j]]<deplca) continue;
vector<signed>w(m,0);
act(v, up[v2][j],0,1e8,w);
act(v, v1,0,1e8,w);
if(ask(w)==k*B) v2=up[v2][j];
}
}
else
{
for(int j = 17; j >= 0; j--)
{
vector<signed>w(m,0);
act(v, up[v1][j],0,1e8,w);
if(ask(w)<k*B) v1=up[v1][j];
}
{
vector<signed>w(m,0);
act(v,v1,0,1e8,w);
if(ask(w)<k*B) v1=up[v1][0];
}
for(int j = 17; j >= 0; j--)
{
vector<signed>w(m,0);
act(up[v2][j], v1,0,1e8,w);
if(ask(w)<k*B) v2=up[v2][j];
}
{
vector<signed>w(m,0);
act(v2, v1,0,1e8,w);
if(ask(w)<k*B) v2=up[v2][0];
}
}
answer(v1,v2);
}
void find_pair(signed n, std::vector<signed> U, std::vector<signed> V, signed A, signed B) {
E.assign(n, vector<edge>());
m = U.size();
rep(i,m)
{
E[U[i]].push_back({V[i],i});
E[V[i]].push_back({U[i],i});
}
vector<signed>tmp(m,0);
k=ask(tmp)/A;
findr(0,A,B);
}
