#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, c1=0, c2=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;
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;
}
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);
}
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 cle=leaves[start];
for(int j = 17; j >= 0; j--)
{
vector<signed>w(m,0);
act(v, up[cle][j],0,1e8,w);
if(ask(w)==k*B) cle=up[cle][j];
}
answer(0,cle);
}
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);
}
