#include<bits/stdc++.h>
#include "highway.h"
#define pb push_back
#define fi first
#define se second
using namespace std;
long long a,b,n;const int N=90090;
int pa[N],what[N],in[N];long long l;vector<int>vv;vector<pair<int,int>>v[N];
vector<int>w;
void dfs(int x,int p,long long le)
{
pa[x]=p;
if(le==0){
vv.pb(x);return;
}
for(auto it:v[x])
{
if(it.se==p)continue;
dfs(it.fi,it.se,le-1);
}
}
int ch(int ll,int r)
{
w.clear();
for(int i=0;i<n-1;i++)w.pb(0);
for(int i=ll;i<=r;i++)
{
w[pa[vv[i]]]=1;
}
long long x=ask(w);
w.clear();
long long y=a*l;
if(x>y)return 1;
return 0;
}
int chee(int ll,int r)
{
w.clear();
for(int i=0;i<n-1;i++)w.pb(0);
for(int i=ll;i<=r;i++)
{
w[pa[what[i]]]=1;
}
long long x=ask(w);
w.clear();
long long y=a*l;
if(x>y)return 1;
return 0;
}
int timer=-1;
void go (int x,int p)
{
pa[x]=p;
in[x]=++timer;
what[timer]=x;
for(auto it:v[x])
{
if(it.se==p)continue;
go(it.fi,it.se);
}
}
void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
a=A;b=B;
w.clear();
n=N;
for(int i=0;i<n-1;i++)w.pb(0);
l=ask(w)/a;
for(int i=0;i<n-1;i++)
{
v[V[i]].pb({U[i],i});
v[U[i]].pb({V[i],i});
}
go(0,-1);
int st=0,end=timer;
while(st<end)
{
int mid=(st+end)/2;
if(chee(mid+1,end))
{
st=mid+1;
}
else end=mid;
}
int point=what[st];
dfs(point,-1,l);
int m=vv.size();
st=0,end=m-1;
while(st<end)
{
int mid=st+end;mid/=2;
if(ch(st,mid)) end=mid;
else st=mid+1;
}
answer(point,vv[st]);
}
/*
4 3
1 2
1 2
1 2
1 0
1 3
*/
