#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
const int mxN=9e4;
int m, d1[mxN], d2[mxN];
vector<int> eu, ev, adj[mxN], bv;
vector<array<int, 2>> p1, p2;
long long bc;
void bfs(int s, int d[mxN], vector<array<int, 2>> &p) {
memset(d, 0x3f, 4*mxN);
d[s]=0;
p.push_back({s});
for(int qh=0; qh<p.size(); ++qh) {
int u=p[qh][0];
for(int e : adj[u]) {
int v=eu[e]^ev[e]^u;
if(d[v]>d[u]+1) {
d[v]=d[u]+1;
p.push_back({v, e});
}
}
}
}
int solve(int d1[mxN], int d2[mxN], vector<array<int, 2>> p) {
vector<array<int, 2>> q;
for(array<int, 2> a : p)
if(d1[a[0]]<d2[a[0]])
q.push_back(a);//, cout << a[0] << " " << a[1] << endl;
int lb=0, rb=q.size()-1;
while(lb<rb) {
int mb=(lb+rb+1)/2;
vector<int> w=bv;
for(int i=mb; i<q.size(); ++i)
w[q[i][1]]=1;
if(ask(w)>bc)
lb=mb;
else
rb=mb-1;
}
return q[lb][0];
}
void find_pair(int n, vector<int> u, vector<int> v, int a, int b) {
eu=u;
ev=v;
m=u.size();
for(int i=0; i<m; ++i) {
adj[u[i]].push_back(i);
adj[v[i]].push_back(i);
}
bv=vector<int>(m);
bc=ask(bv);
int lb=0, rb=m-1;
while(lb<rb) {
int mb=(lb+rb)/2;
vector<int> w=bv;
fill(w.begin(), w.begin()+mb+1, 1);
if(ask(w)>bc)
rb=mb;
else
lb=mb+1;
}
//cout << lb << endl;
fill(bv.begin(), bv.begin()+lb, 1);
bfs(u[lb], d1, p1);
bfs(v[lb], d2, p2);
answer(solve(d1, d2, p1), solve(d2, d1, p2));
}
