//#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<llo> adj2[100001];
vector<pair<llo,llo>> lev[100001];
llo dist[100001];
llo ba[100001];
llo vis[100001];
llo vis2[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 dfs2(int no){
vis2[no]=1;
for(auto j:adj2[no]){
if(vis2[j]==0){
dfs2(j);
}
}
}
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){
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++){
if(dist[i]==-1){
vis2[i]=2;
}
}
for(int i=0;i<n;i++){
for(auto j:adj[i]){
if(dist[i]==-1 or dist[j.a]==-1){
continue;
}
if(dist[j.a]==dist[i]-1){
adj2[j.a].pb(i);
}
}
}
dfs2(no.b);
for(int i=0;i<n;i++){
if(vis2[i]==0){
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)<=tt.size()){
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 and dist[k.a]!=-1){
cur2[k.b]=1;
}
}
}
if(ask(cur2)==ans){
low+=(1<<j);
}
}
}
int xx=tt[low].b;
tt.clear();
for(int i=0;i<n;i++){
if(vis2[i]==1){
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)<=tt.size()){
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 and dist[k.a]!=-1){
cur2[k.b]=1;
}
}
}
if(ask(cur2)==ans){
low+=(1<<j);
}
}
}
/* llo zz=xx;
while(zz>=0){
vis[zz]=1;
zz=ba[zz];
}
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++){
if(vis[tt[i].b]==1){
// cout<<tt[i].b<<"???"<<endl;
continue;
}
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);
}
}
}*/
// 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);*/
}
