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