#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ll long long
long long ask(const std::vector<int> &w);
void answer(int s, int t);
const ll NP=1e5;
vector<pair<ll,ll>> ma[NP],tmp;
vector<int> w;
ll mi,a,b,par[NP],vis[NP];
ll wantd;
vector<int> ans;
void dfs(int x,int p=-1,ll d=0)
{
par[x]=p;
if(d==(wantd))
ans.pb(x);
for(auto y:ma[x])
{
if(y.second!=p)
{
dfs(y.second,x,d+1);
}
}
}
map<pair<int,int>,int> edg;
void find_pair(int n, std::vector<int> u, std::vector<int> v, int A, int B)
{
int m=u.size();
w.resize(m,0);
a=A;
b=B;
mi=ask(w);
wantd=(mi/a);
for(int i=0;i<n;i++)
ma[i].clear();
for(int i=0;i<m;i++)
{
edg[{u[i],v[i]}]=i;
edg[{v[i],u[i]}]=i;
ma[u[i]].pb({i,v[i]});
ma[v[i]].pb({i,u[i]});
}
dfs(0);
int s=-1;
int e=ans.size();
while(s+1<e)
{
int mid=(s+e)/2;
for(int i=0;i<n;i++)
vis[i]=0;
vector<int> cur;
for(int j=s+1;j<=mid;j++)
{
int s=ans[j];
while(s!=0)
{
if(vis[s])break;
vis[s]=1;
cur.push_back(edg[{s,par[s]}]);
s=par[s];
}
}
for(auto i:cur)
w[i]=1;
ll wa=ask(w);
for(auto i:cur)
w[i]=0;
if(wa==(b*wantd))
{
e=mid;
}
else
{
s=mid;
}
}
answer(0,ans[e]);
}
