#include <bits/stdc++.h>
#include "highway.h"
using namespace std;
#define pb push_back
#define ss second
#define ff first
#define sz(a) int(a.size())
#define all(a) a.begin(),a.end()
typedef long double ld;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
const ll inf = 1e18;
const int mod = 1e9+7; //998244353;
const int maxn = 1e5+5;
const int Xg[4] = {1,0,-1,0}, Yg[4] = {0,1,0,-1};
ll modpw(ll a,ll e) {if(e==0)return 1;ll x=modpw(a*a%mod,e>>1);return e&1?x*a%mod:x;}
int M;
vi col;
ll init;
queue<pii>q;
int dis[maxn],us[maxn];
pii par[maxn];
vector<pii> adj[maxn],E[maxn];
vi v[3],cl;
void bfs(int nd,int nd1){
q.push({nd,0});
q.push({nd1,1});
while(!q.empty()){
pii x = q.front();
v[x.ss].pb(x.ff);
q.pop();
for(auto i : adj[x.ff]){
if(dis[i.ff] > dis[x.ff]+1){
dis[i.ff]=dis[x.ff]+1;
par[i.ff]={i.ss,x.ff};
us[i.ss]=1;
q.push({i.ff,x.ss});
}
}
}
}
int bin(int tp){
int l=1,r=sz(v[tp])-1,md,jog=0;
while(l <= r){
md=(l+r)/2;
for(int i = 0;i < M;i++) col[i]=0;
for(auto i : cl) col[i] = 1;
for(int i = md;i <= r;i++) if(par[v[tp][i]].ff!=-1) col[par[v[tp][i]].ff]=1;
if(ask(col) > init) jog=md,l=md+1;
else r=md-1;
}
return v[tp][jog];
}
void find_pair(int N, vi U, vi V, int A, int B) {
M = sz(U); col.resize(M);
for(int i = 0;i < M;i++){
adj[U[i]].pb({V[i],i});
adj[V[i]].pb({U[i],i});
}
init = ask(col);
int l = 0,r = M-1,md,jog=M-1;
while(l < r){
md = (l+r)/2;
for(int i = 0;i <= md;i++) col[i]=1;
for(int i = md+1;i < M;i++) col[i]=0;
ll now=ask(col);
if(now > init) r=md-1,jog=md;
else l=md+1;
}
r=jog;
// cout<<U[r]<<' '<<V[r]<<'\n';
for(int i=0;i<N;i++) dis[i]=mod;
dis[U[r]]=0;
dis[V[r]]=0;
par[U[r]].ff=-1;
par[V[r]].ff=-1;
bfs(U[r],V[r]);
// for(int i = 0;i < N;i++) cout<<par[i].ff<<' ';
// cout<<'\n';
us[r]=1;
for(int i = 0;i < M;i++) if(!us[i]) cl.pb(i);
// for(auto i : v[0]) cout<<i<<' ';
// cout<<" --\n";
// for(auto i : v[1]) cout<<i<<' ';
// cout<<'\n';
int ans=bin(0);
int ans1=bin(1);
// cout<<ans<<' '<<ans1<<'\n';
answer(ans,ans1);
}
