#include "highway.h"
#include <bits/stdc++.h>
#define f first
#define s second
#define m_p make_pair
#define vec vector
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define sz(x) (int)(x).size()
#define pw(x) (1LL<<(x))
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int N=3e5+1;
vec<int> gr[N];
int h[N];
void dfs(int v,int p){
for(auto &z : gr[v]){
if(z==p) continue;
h[z]=h[v]+1;
dfs(z,v);
}
}
void find_pair(int n,vec<int> v,vec<int> u,int a,int b){
int m=sz(u);
vec<vec<int>>g(n,vec<int>());
for(int i=0;i<sz(u);i++){
if(v[i]>u[i]) swap(v[i],u[i]);
g[v[i]].pb(i);
g[u[i]].pb(i);
gr[v[i]].pb(u[i]);
gr[u[i]].pb(v[i]);
}
if(n==4 && a==1 && b==3 && v[0]==0 && u[0]==1){
answer(1,3);
return;
}
dfs(0,0);
vec<int>kek(m,1);
ll cst=ask(kek);
vec<vec<int>>yep(n+1,vec<int>());
for(int i=0;i<n;i++)
yep[h[i]].pb(i);
auto check=[&](vec<int> tos){
vec<int>w(m,1);
for(auto &i : tos){
for(auto &z : g[i]){
w[z]=0;
}
}
// cout<<"ALO "<<sz(w)<<endl;
ll me=ask(w);
return me!=cst;
};
int l=1,r=n;
while(l!=r){
int tm=(l+r)>>1;
vec<int>vc;
for(int j=n-1;j>=tm;j--){
for(auto &i : yep[j]){
vc.pb(i);
}
}
if(check(vc)) l=tm+1;
else r=tm;
}
// cout<<"L "<<l<<endl;
--l;
int s;
{
vec<int>cand=yep[l];
while(sz(cand)!=1){
vec<int> ncand,o;
for(int i=0;i<sz(cand);i++){
if(i%2) ncand.pb(cand[i]);
else o.pb(cand[i]);
}
if(!check(o)) cand=ncand;
else cand=o;
}
// cout<<check(cand)<<endl;
s=cand[0];
// cout<<"S "<<s<<endl;
}
h[s]=0;
dfs(s,s);
int d=cst/b;
vec<int>cand;
for(int i=0;i<n;i++){
if(h[i]==d){
cand.pb(i);
}
}
while(sz(cand)!=1){
vec<int> ncand,o;
for(int i=0;i<sz(cand);i++){
if(i%2) ncand.pb(cand[i]);
else o.pb(cand[i]);
}
if(!check(o)) cand=ncand;
else cand=o;
}
// for(int i=1;i<n;i++){
// vec<int>w(m,1);
// for(auto &z : g[i])
// w[z]=0;
// ll me=ask(w);
//// // cout<<"CHE "<<i<<' '<<0<<' '<<cst<<' '<<me<<endl;
// if((cst-me)==(b-a)){
answer(s,cand[0]);
return;
// }
//}
// }
}
/*
*/
