#include <bits/stdc++.h>
using namespace std;
using ll=long long;
#define pb push_back
#define rep(i,n) for(int i=0; i<(n); ++i)
#define rrep(i,n) for(int i=1; i<=(n); ++i)
ll ask(const vector<int>&);
void answer(int, int);
vector<int> asking;
int n, m;
vector<int> e[90010];
int es[130010];
ll base;
int find_cut(int l, int r){
if(l == r) return l;
int mid = (l+r)/2;
for(int p=l; p<=mid; ++p) for(int ei:e[p]) asking[ei]=1;
bool res = (ask(asking) > base);
for(int p=l; p<=mid; ++p) for(int ei:e[p]) asking[ei]=0;
if(res) return find_cut(l, mid);
else return find_cut(mid+1, r);
}
int cut;
int q[90010], hd, tl;
bool vis[90010];
int find_deep(int l, int r){
if(l == r){
return q[l];
}
int mid=(l+r)/2;
for(int i=mid+1; i<=r; ++i) for(int ei:e[q[i]]) asking[ei]=1;
bool res = (ask(asking) > base);
for(int i=mid+1; i<=r; ++i) for(int ei:e[q[i]]) asking[ei]=0;
if(res) return find_deep(mid+1, r);
else return find_deep(l, mid);
}
bool dead[90010];
void muko(int x){
dead[x]=1;
for(int ei:e[x]){
int y=es[ei]-x;
if(y==cut) continue;
if(!dead[y]){
muko(y);
}
}
}
void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
// find cut vertex
n = N;
m = U.size();
asking.resize(m);
base = ask(asking);
for(int i=0; i<m; ++i){
int a = U[i], b = V[i];
e[a].pb(i); e[b].pb(i);
es[i]=a+b;
}
cut = find_cut(0, n-1);
q[hd++] = cut;
vis[cut]=1;
while(hd>tl){
int x=q[tl++];
for(int ei:e[x]){
int y=es[ei]-x;
if(!vis[y]){
vis[y]=1;
q[hd++]=y;
}
}
}
int deep = find_deep(0, n-1);
muko(deep);
hd=tl=0;
q[hd++] = cut;
fill(vis, vis+n, 0);
vis[cut]=1;
while(hd>tl){
int x=q[tl++];
for(int ei:e[x]){
int y=es[ei]-x;
if(dead[y]) continue;
if(!vis[y]){
vis[y]=1;
q[hd++]=y;
}
}
}
int d2 = find_deep(0, hd-1);
answer(deep, d2);
}
