#include <bits/stdc++.h>
#include "highway.h"
using namespace std;
#define MAXN 90001
int n,m,a,b;
vector<pair<int,int>> adj[MAXN];
pair<int,int> parent[MAXN];
int dist[MAXN];
vector<int> possibilities;
vector<int> state;
vector<int> nodes[MAXN];
void dfs(int node,int pret,int edge,int depth)
{
parent[node]={pret,edge};dist[node]=depth;
for (pair<int,int> sled:adj[node])
{
if (sled.first!=pret) dfs(sled.first,node,sled.second,depth+1);
}
}
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B)
{
n=N,m=(int)U.size(),a=A,b=B;
for (int i=0;i<m;i++) {adj[U[i]].push_back({V[i],i});adj[V[i]].push_back({U[i],i});}
dfs(0,-1,-1,0);for (int i=0;i<m;i++) state.push_back(0);
int distancija=((long long)ask(state))/a;
if (m==n-1)
{
int maxdist=-1;
for (int node=0;node<n;node++) {nodes[dist[node]].push_back(node);maxdist=max(maxdist,dist[node]);}
int l=distancija,r=maxdist,rez=-1;
while (l<=r)
{
int mid=(l+r)/2;
for (int i=mid;i<=maxdist;i++)
{
for (int node:nodes[i]) state[parent[node].second]=1;
}
long long ans=ask(state);
if (ans==(long long)a*distancija) r=mid-1;
else if (ans==(long long)b*distancija) {rez=mid;l=mid+1;}
else
{
int bra=((long long)b*distancija-ans)/(b-a);int brb=distancija-bra;
rez=mid+brb-1;break;
}
for (int i=mid;i<=maxdist;i++)
{
for (int node:nodes[i]) state[parent[node].second]=0;
}
}
for (int node:nodes[rez]) possibilities.push_back(node);
l=0,r=(int)possibilities.size()-1,rez=-1;
while (l<=r)
{
int mid=(l+r)/2;
for (int i=mid;i<(int)possibilities.size();i++) state[parent[possibilities[i]].second]=1;
long long ans=ask(state);
if (ans==(long long)a*distancija) r=mid-1;
else {rez=mid;l=mid+1;}
for (int i=mid;i<(int)possibilities.size();i++) state[parent[possibilities[i]].second]=0;
}
int current=possibilities[rez];int number=0;
while (number<distancija) {current=parent[current].first;number++;}
answer(current,possibilities[rez]);return;
}
bool subtask1=true;if (m!=n-1) subtask1=false;
for (int i=0;i<m;i++)
{
if (!(U[i]==i and V[i]==i+1)) {subtask1=false;break;}
}
if (subtask1)
{
int l=distancija-1,r=m-1,rez=-1;
while (l<=r)
{
int mid=(l+r)/2;
for (int i=mid;i<m;i++) state[i]=1;
long long ans=ask(state);
if (ans==(long long)a*distancija) r=mid-1;
else if (ans==(long long)b*distancija) {rez=mid;l=mid+1;}
else
{
int bra=((long long)b*distancija-ans)/(b-a);int brb=distancija-bra;
answer(mid-bra,mid+distancija-bra);/*cout<<mid-bra<<" "<<mid+distancija-bra<<endl;*/return;
}
for (int i=mid;i<m;i++) state[i]=0;
}
answer(rez-distancija,rez);/*cout<<rez<<" "<<rez+distancija<<endl;*/return;
}
for (int node=1;node<n;node++)
{
if (dist[node]==distancija) possibilities.push_back(node);
}
if (n<=100)
{
for (int node:possibilities)
{
int current=node;while (current!=0) {state[parent[current].second]=1;current=parent[current].first;}
long long ans=ask(state);if (ans==(long long)b*distancija) {answer(0,node);return;}
current=node;while (current!=0) {state[parent[current].second]=0;current=parent[current].first;}
}
}
int l=0,r=(int)possibilities.size()-1,rez=-1;
while (l<=r)
{
int mid=(l+r)/2;
for (int i=mid;i<(int)possibilities.size();i++) state[parent[possibilities[i]].second]=1;
long long ans=ask(state);
if (ans==(long long)a*distancija) r=mid-1;
else {rez=mid;l=mid+1;}
for (int i=mid;i<(int)possibilities.size();i++) state[parent[possibilities[i]].second]=0;
}
answer(0,possibilities[rez]);return;
}
