//#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define mp make_pair
#define pb push_back
#define a first
#define b second
#define endl '\n'
#include "highway.h"
vector<int> cur;
vector<pair<llo,llo>> adj[100001];
vector<pair<llo,llo>> lev[100001];
llo dist[100001];
llo ba[100001];
llo vis[100001];
void dfs(llo no,llo par=-1,llo levv=0,llo la=-1){
lev[levv].pb({no,la});
for(auto j:adj[no]){
if(j.a!=par){
dfs(j.a,no,levv+1,j.b);
}
}
}
void find_pair(int n, std::vector<int> uu, std::vector<int> vv, int aa, int bb) {
int m=uu.size();
for(int i=0;i<m;i++){
cur.pb(0);
}
llo ans=ask(cur);
for(int i=0;i<m;i++){
adj[uu[i]].pb({vv[i],i});
adj[vv[i]].pb({uu[i],i});
}
llo low=0;
for(int j=19;j>=0;j--){
if(low+(1LL<<j)<=m){
vector<int> cur2=cur;
for(int i=0;i<low+(1<<j);i++){
cur2[i]=1;
}
if(ask(cur2)==ans){
low+=(1<<j);
}
}
}
for(int i=0;i<low;i++){
if((aa==1 and bb==2)){
cur[i]=1;
}
}
//return;
pair<int,int> no={uu[low],vv[low]};
for(int i=0;i<n;i++){
dist[i]=-1;
ba[i]=-1;
}
queue<int> ss;
ss.push(no.a);
dist[no.a]=0;
while(ss.size()){
int cot=ss.front();
ss.pop();
for(auto j:adj[cot]){
if(j.b<low and (aa==1 and bb==2)){
continue;
}
if(dist[j.a]==-1){
dist[j.a]=dist[cot]+1;
ba[j.a]=cot;
ss.push(j.a);
}
}
}
vector<pair<int,int>> tt;
for(int i=0;i<n;i++){
tt.pb({dist[i],i});
}
sort(tt.begin(),tt.end());
reverse(tt.begin(),tt.end());
low=0;
for(int j=19;j>=0;j--){
if(low+(1<<j)<=n){
vector<int> cur2=cur;
for(int i=0;i<low+(1<<j);i++){
int x=tt[i].b;
for(auto k:adj[x]){
if(dist[k.a]==dist[x]-1){
cur2[k.b]=1;
}
}
}
if(ask(cur2)==ans){
low+=(1<<j);
}
}
}
int xx=tt[low].b;
//cout<<no.a<<":"<<no.b<<endl;
//cout<<xx<<":"<<endl;
if(dist[xx]==(ans/(llo)aa)){
answer(xx,no.a);
return;
}
llo zz=xx;
while(zz>=0){
vis[zz]=1;
//cout<<zz<<".";
zz=ba[zz];
}
//cout<<endl;
low=0;
/*for(auto j:tt){
cout<<j.a<<"<<"<<j.b<<endl;
}
cout<<endl<<endl;
for(int i=0;i<n;i++){
cout<<dist[i]<<"<";
}
cout<<endl;*/
for(int j=19;j>=0;j--){
if(low+(1<<j)<=n){
vector<int> cur2=cur;
for(int i=0;i<low+(1<<j);i++){
if(vis[tt[i].b]==1){
// cout<<tt[i].b<<"???"<<endl;
continue;
}
int x=tt[i].b;
for(auto k:adj[x]){
/*if(tt[i].b==3){
cout<<k.a<<"{{"<<k.b<<endl;
cout<<dist[k.a]<<"}}"<<dist[x]<<endl;
}*/
if(dist[k.a]==dist[x]-1){
cur2[k.b]=1;
/* if(tt[i].b==3){
cout<<k.b<<"!!"<<endl;
}*/
}
}
}
if(ask(cur2)==ans){
/*cout<<low+(1<<j)<<":::"<<endl;
for(auto ii:cur2){
cout<<ii;
}
cout<<endl;
cout<<ask(cur2)<<endl;*/
low+=(1<<j);
}
}
}
// cout<<low<<endl;
//cout<<tt[low].b<<",,"<<endl;
answer(xx,tt[low].b);
/* int l=0;
int r=m-1;
while(l<r){
int mid=(l+r)/2;
vector<int> cur2=cur;
for(int i=l;i<=mid;i++){
cur2[i]=1;
}
if(ask(cur2)==ans){
l=mid+1;
}
else{
r=mid;
}
}
//return;
pair<int,int> no={uu[l],vv[l]};
for(int i=0;i<=n;i++){
lev[i].clear();
}
dfs(no.a,no.b,0,l);
vector<pair<llo,llo>> ord;
for(int i=n;i>=0;i--){
for(auto j:lev[i]){
ord.pb(j);
}
}
llo low=0;
for(int j=19;j>=0;j--){
if(low+(1<<j)<=ord.size()){
vector<int> cur2=cur;
for(int i=0;i<low+(1<<j);i++){
cur2[ord[i].b]=1;
}
if(ask(cur2)==ans){
low+=(1<<j);
}
}
}
int xx=ord[low].a;
ord.clear();
for(int i=0;i<=n;i++){
lev[i].clear();
}
dfs(no.b,no.a,0,l);
for(int i=n;i>=0;i--){
for(auto j:lev[i]){
ord.pb(j);
}
}
low=0;
for(int j=19;j>=0;j--){
if(low+(1<<j)<=ord.size()){
vector<int> cur2=cur;
for(int i=0;i<low+(1<<j);i++){
cur2[ord[i].b]=1;
}
if(ask(cur2)==ans){
low+=(1<<j);
}
}
}
int yy=ord[low].a;
answer(xx,yy);*/
}
