#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> nodes[MAXN];
vector<int> state;
void dfs(int node,int pret,int edge,int depth)
{
parent[node]={pret,edge};dist[node]=depth;nodes[depth].push_back(node);
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});}
if (m!=n-1) {answer(0,0);return;}
dfs(0,-1,-1,0);for (int i=0;i<m;i++) state.push_back(0);
int distancija=((long long)ask(state))/a;
int maxdist=0;for (int node=0;node<n;node++) maxdist=max(maxdist,dist[node]);
int l=1,r=maxdist,rez=0;
while (l<=r)
{
int mid=(l+r)/2;
for (int distanca=0;distanca<=mid;distanca++)
{
for (int node:nodes[distanca])
{
if (parent[node].second!=-1) state[parent[node].second]=1;
}
}
long long curr=ask(state);
if (curr==(long long)a*distancija) {rez=mid;l=mid+1;}
else r=mid-1;
for (int distanca=0;distanca<=mid;distanca++)
{
for (int node:nodes[distanca])
{
if (parent[node].second!=-1) state[parent[node].second]=0;
}
}
}
int depthlca=rez;
l=depthlca+1,r=maxdist,rez=depthlca;
while (l<=r)
{
int mid=(l+r)/2;
for (int distanca=0;distanca<=mid;distanca++)
{
for (int node:nodes[distanca])
{
if (parent[node].second!=-1) state[parent[node].second]=1;
}
}
long long curr=ask(state);
if (curr==(long long)b*distancija) {rez=mid;r=mid-1;}
else l=mid+1;
for (int distanca=0;distanca<=mid;distanca++)
{
for (int node:nodes[distanca])
{
if (parent[node].second!=-1) state[parent[node].second]=0;
}
}
}
int depthnode1=rez;int depthnode2=2*depthlca+distancija-depthnode1;
if (depthnode1==depthnode2)
{
l=0,r=(int)nodes[depthnode1].size()-1,rez=-1;
while (l<=r)
{
int mid=(l+r)/2;
for (int pos=0;pos<=mid;pos++)
{
int node=nodes[depthnode1][pos];
if (parent[node].second!=-1) state[parent[node].second]=1;
}
long long sol=ask(state);
if (sol==(long long)a*distancija+(b-a)) {rez=mid;r=mid-1;}
else if (sol==(long long)a*distancija+2*(b-a)) r=mid-1;
else l=mid+1;
for (int pos=0;pos<=mid;pos++)
{
int node=nodes[depthnode1][pos];
if (parent[node].second!=-1) state[parent[node].second]=0;
}
}
int node1=nodes[depthnode1][rez];
l=rez+1,r=(int)nodes[depthnode1].size()-1;rez=-1;
while (l<=r)
{
int mid=(l+r)/2;
for (int pos=0;pos<=mid;pos++)
{
int node=nodes[depthnode1][pos];
if (parent[node].second!=-1) state[parent[node].second]=1;
}
long long sol=ask(state);
if (sol==(long long)a*distancija+2*(b-a)) {rez=mid;r=mid-1;}
else l=mid+1;
for (int pos=0;pos<=mid;pos++)
{
int node=nodes[depthnode1][pos];
if (parent[node].second!=-1) state[parent[node].second]=0;
}
}
int node2=nodes[depthnode1][rez];
answer(node1,node2);return;
}
l=0,r=(int)nodes[depthnode1].size()-1,rez=-1;
while (l<=r)
{
int mid=(l+r)/2;
for (int pos=0;pos<=mid;pos++)
{
int node=nodes[depthnode1][pos];
if (parent[node].second!=-1) state[parent[node].second]=1;
}
long long sol=ask(state);
if (sol==(long long)a*distancija+(b-a)) {rez=mid;r=mid-1;}
else l=mid+1;
for (int pos=0;pos<=mid;pos++)
{
int node=nodes[depthnode1][pos];
if (parent[node].second!=-1) state[parent[node].second]=0;
}
}
int node1=nodes[depthnode1][rez];
if (depthnode2==depthlca)
{
int node2=node1;int number=0;
while (number<distancija) {node2=parent[node2].first;number++;}
answer(node1,node2);return;
}
int stopnode=node1;int number=0;
while (number<depthnode1-depthnode2) {stopnode=parent[stopnode].first;number++;}
l=0,r=(int)nodes[depthnode2].size()-1,rez=-1;
while (l<=r)
{
int mid=(l+r)/2;
for (int pos=0;pos<=mid;pos++)
{
int node=nodes[depthnode2][pos];if (node==stopnode) continue;
if (parent[node].second!=-1) state[parent[node].second]=1;
}
long long sol=ask(state);
if (sol==(long long)a*distancija+(b-a)) {rez=mid;r=mid-1;}
else l=mid+1;
for (int pos=0;pos<=mid;pos++)
{
int node=nodes[depthnode2][pos];if (node==stopnode) continue;
if (parent[node].second!=-1) state[parent[node].second]=0;
}
}
int node2=nodes[depthnode2][rez];
answer(node1,node2);
}
