#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
vector<vector<ll>> adj;
map<ll,map<ll,ll>> M;
vector<ll> depth,parent;
vector<vector<ll>> prof;
vector<int> w;
ll n;
void dfs(ll cur, ll prev) {
prof[depth[cur]].push_back(cur);
parent[cur]=prev;
for (ll v:adj[cur]) {
if (v!=prev){
depth[v]=depth[cur]+1;
dfs(v, cur);
}
}
}
/*int ask(int w[]){
return 1;
}
void answer(ll x,ll y){
cout<<x;
}*/
ll chance(ll cur){
ll l,r,m;
l=0;
vector<ll> hijos;
for (auto x:adj[cur]) {
if (x!= parent[cur]) {
hijos.push_back(x);
}
}
r=hijos.size();
while(l<r){
m=(l+r)/2;
for(ll i=0;i<=m;i++){
w[M[cur][hijos[i]]]=0;
}
for(ll i=m+1;i<hijos.size();i++){
w[M[cur][hijos[i]]]=1;
}
ll ans1=ask(w);
for(ll i=0;i<=m;i++){
w[M[cur][hijos[i]]]=1;
}
for(ll i=m+1;i<hijos.size();i++){
w[M[cur][hijos[i]]]=0;
}
ll ans2=ask(w);
if(ans1==ans2){
return -1;
}else if(ans1<ans2){
l=m+1;
}else{
r=m;
}
}
return hijos[l];
}
void find_pair(int N,vector<int> U,vector<int> V, int A, int B){
adj.resize(N);
prof.resize(N);
depth.resize(N);
w.resize(N);
n=N;
for(ll i=0;i<N;i++){
w[i]=0;
}
for(int i=0;i<N-1;i++){
adj[U[i]].push_back(V[i]);
adj[V[i]].push_back(U[i]);
M[U[i]][V[i]]=i;
M[V[i]][U[i]]=i;
}
ll xd=ask(w);
ll a=xd/A;
depth[0]=0;
dfs(0, -1);
ll b=a-1;
for(auto x:prof[b]){
ll ans=chance(x);
if(ans!=-1){
answer(0,ans);
}
}
}
