#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> distu[90005], distv[90005], vec;
vector<pair<int, int> > adj[90005];
pair<int, int> par[90005];
void dfs(int u, int p, int d, bool b)
{
if (b)
distu[d].push_back(u);
else
distv[d].push_back(u);
for (int i=0; i<adj[u].size(); i++)
{
int v=adj[u][i].first, w=adj[u][i].second;
if (v!=p)
{
par[v]={u, w};
dfs(v, u, d+1, b);
}
}
}
void find_pair(int n, vector<int> u, vector<int> v, int a, int b)
{
for (int i=0; i<=n-2; i++)
vec.push_back(0);
long long res=ask(vec)/a;
int l=0, r=n-2, d, ans;
while (l<r)
{
int mid=(l+r)/2;
for (int i=0; i<=n-2; i++)
vec[i]=0;
for (int i=l; i<=mid; i++)
vec[i]=1;
if (ask(vec)==res*a)
l=mid+1;
else
r=mid;
}
for (int i=0; i<=n-2; i++)
{
if (i!=l)
{
adj[u[i]].push_back({v[i], i});
adj[v[i]].push_back({u[i], i});
}
}
dfs(u[l], -1, 0, 1);
dfs(v[l], -1, 0, 0);
l=0, r=n-2;
while (l<r)
{
int mid=(l+r+1)/2;
for (int i=0; i<=n-2; i++)
vec[i]=0;
for (int i=mid; i<=r; i++)
for (int j:distu[i])
vec[par[j].second]=1;
if (ask(vec)==res*a)
r=mid-1;
else
l=mid;
}
d=l;
l=0, r=distu[d].size()-1;
while (l<r)
{
int mid=(l+r)/2;
for (int i=0; i<=n-2; i++)
vec[i]=0;
for (int i=l; i<=mid; i++)
vec[par[distu[d][i]].second]=1;
if (ask(vec)==res*a)
l=mid+1;
else
r=mid;
}
ans=distu[d][l];
d=res-d-1;
l=0, r=distv[d].size()-1;
while (l<r)
{
int mid=(l+r)/2;
for (int i=0; i<=n-2; i++)
vec[i]=0;
for (int i=l; i<=mid; i++)
vec[par[distv[d][i]].second]=1;
if (ask(vec)==res*a)
l=mid+1;
else
r=mid;
}
answer(ans, distv[d][l]);
}
