#include "highway.h"
#include <iostream>
#include <vector>
using namespace std;
const int MAXN=1e5+10;
vector <pair <int,int> > v[MAXN], dist;
vector <int> w;
int edge;
long long path;
int n;
long long a, b;
void find_tree(int x, int par) {
for (auto i:v[x]) {
if (i.second==edge) continue;
if (i.first==par) continue;
w[i.second]=1;
find_tree(i.first,x);
}
}
void dfs(int x, int par, int d) {
for (auto i:v[x]) {
if (i.second==edge) continue;
if (i.first==par) continue;
if (d==1) {
dist.push_back(i);
continue;
}
dfs(i.first,x,d-1);
}
}
int find_one(int start) {
for (int i=0;i<n-1;i++) w[i]=0;
find_tree(start,start);
int d=(ask(w)-path)/(b-a);
if (d==0) return start;
if (!dist.empty()) dist.clear();
dfs(start,start,d);
int l, r, mid;
l=0; r=dist.size()-1;
while (l<r) {
mid=(l+r)/2;
for (int i=0;i<n-1;i++) w[i]=0;
for (int i=l;i<=mid;i++) w[dist[i].second]=1;
long long cur=ask(w);
if (cur==path) l=mid+1;
else r=mid;
}
return dist[l].first;
}
void find_pair (int N, vector <int> U, vector <int> V, int A, int B) {
n=N; a=A; b=B;
w.resize(n-1);
for (int i=0;i<n-1;i++) {
v[U[i]].push_back({V[i],i});
v[V[i]].push_back({U[i],i});
}
for (int i=0;i<n-1;i++) w[i]=0;
path=ask(w);
//cout << path << endl;
int l, r, mid;
l=0; r=n-1;
while (l<r) {
mid=(l+r)/2;
for (int i=0;i<n-1;i++) w[i]=0;
for (int i=l;i<=mid;i++) w[i]=1;
long long cur=ask(w);
if (cur==path) l=mid+1;
else r=mid;
}
edge=l;
//cout << U[edge] << ' ' << V[edge] << endl;
int ans1, ans2;
ans1=find_one(U[edge]);
ans2=find_one(V[edge]);
answer(ans1,ans2);
}
