#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
vector<pair<int, int> > adj[90005];
pair<int, int> par[90005];
vector<int> vu, vv, vec;
void dfs(int u, int p, int d, bool b)
{
if (b)
vu.push_back(u);
else
vv.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, 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=vu.size()-1;
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++)
vec[par[vu[i]].second]=1;
if (ask(vec)==res*a)
r=mid-1;
else
l=mid;
}
ans=vu[l];
l=0, r=vv.size()-1;
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++)
vec[par[vv[i]].second]=1;
if (ask(vec)==res*a)
r=mid-1;
else
l=mid;
}
answer(ans, vv[l]);
}
