#include "highway.h"
#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define all(x) x.begin(),x.end()
typedef long long ll;
#define INF 99999999999999
#define pb push_back
vector<vector<pair<int,int>>>g;
vector<int>d,R;
void dfs(int start,int pre)
{
for(pair<int,int> x:g[start])
if(x.F!=pre)
{
d[x.F]=d[pre]+1;
R[x.F]=x.S;
dfs(x.F,start);
}
}
void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
int M = U.size();
g.assign(N,vector<pair<int,int>>());
d.assign(N,0);
R.assign(N,0);
for(int i=0;i<M;i++)
{
g[U[i]].pb({V[i],i});
g[V[i]].pb({U[i],i});
}
dfs(0,0);
vector<int>a(M);
ll ans=ask(a);
vector<int>v;
for(int i=1;i<N;i++)
if(d[i]==ans/A)
v.pb(R[i]);
ll l=0,r=v.size()-1;
ll idx=0;
while(l<r)
{
ll mid=(l+r)/2;
for(int i=l;i<=mid;i++)
a[i]=(idx+1)%2;
ll curr=ask(a);
if(idx==0)
{
if(curr>ans)
{
r=mid;
idx=1;
}
else
l=mid+1;
}
else
{
if(curr<ans)
{
r=mid;
idx=0;
}
else
l=mid+1;
}
}
for(int i=1;i<N;i++)
if(R[i]==l)
{
ans=i;
break;
}
answer(0,ans);
}
