#include "highway.h"
#include<bits/stdc++.h>
using namespace std;
using pii=pair<int,int>;
using ll=long long;
#define eb emplace_back
int N,M;
vector<pii> adj[90005],adj2[90005];
vector<int> temp,ans;
pii edge[130005];
bool flag[90005];
int tour[90005],node[90005],id0;
ll mn;
void bfs(int u){
queue<int> q;
q.push(u);
flag[u]=1;
while(q.size()){
int u=q.front(); q.pop();
tour[u]=++id0;
node[id0]=u;
for(auto &[v,i]:adj[u]){
if(!flag[v]){
q.push(v);
flag[v]=1;
adj2[u].eb(v,i),adj2[v].eb(u,i);
}
}
}
}
void dfs(int u,int p){
tour[u]=++id0;
node[id0]=u;
for(auto &[v,i]:adj2[u]){
if(v!=p) dfs(v,u);
}
}
int play(int U){
for(int i=0;i<N;++i) adj2[i].clear(),flag[i]=0;
id0=0;
bfs(U);
// id0=0,dfs(U,U);
int l=1,r=id0;
while(l<r){
int mid=l+((r-l)>>1);
for(int i=0;i<M;++i){
auto &[u,v]=edge[i];
if(tour[u]<=mid&&tour[v]<=mid) temp[i]=0;
else temp[i]=1;
}
if(ask(temp)==mn) r=mid;
else l=mid+1;
}
ans.eb(node[l]);
return node[l];
}
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
::N=N,M=U.size();
for(int i=0;i<M;++i){
adj[U[i]].eb(V[i],i);
adj[V[i]].eb(U[i],i);
edge[i]={U[i],V[i]};
temp.eb(0);
}
mn=ask(temp);
play(play(0));
answer(ans[0],ans[1]);
}
