#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
//macros
typedef long long ll;
typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<ll> vll;
#define REP(a,b,c) for(int a=int(b); a<int(c); a++)
#define RE(a,c) REP(a,0,c)
#define RE1(a,c) REP(a,1,c+1)
#define REI(a,b,c) REP(a,b,c+1)
#define REV(a,b,c) for(int a=int(c-1); a>=int(b); a--)
#define pb push_back
#define fi first
#define se second
#define sz size()
//===================//
// begin program //
//===================//
const int MX = 5e5;
int n, m, a, b;
vi w, u, v;
vii adj[MX], chl[MX];
ll dist;
vi onPath, visited;
int getS(int root) {
// bfs
visited.assign(n, 0);
vii binS;
queue<int> q;
q.push(root); visited[root] = 1;
while(!q.empty()) {
int u = q.front(); q.pop();
for(ii v : adj[u]) {
if(visited[v.fi]) continue;
visited[v.fi] = 1;
q.push(v.fi);
chl[u].pb(v);
binS.pb(v);
}
}
// binaray search for s
int lb=0, ub=binS.sz-1;
while(lb != ub) {
int mid=(lb+ub+1)/2;
RE(i,m) w[i] = 1;
RE(i,mid) w[binS[i].se] = 0;
if(ask(w) == dist) ub = mid-1;
else lb = mid;
}
return binS[lb].fi;
}
void find_pair(int N, vi U, vi V, int A, int B) {
n=N; a=A; b=B; u=U; v=V;
m = u.sz;
w.assign(m, 0);
RE(i,m) {
adj[u[i]].pb({v[i], i});
adj[v[i]].pb({u[i], i});
}
dist = ask(w);
// get vertex w on path s - t
onPath.assign(n, 1);
int ones = n;
while(ones != 1) {
set<int> rem;
RE(i,n) if(onPath[i] && rem.sz < ones/2) {
onPath[i]=0;
rem.insert(i);
}
RE(i,m) {
if(onPath[u[i]] || onPath[v[i]]) w[i] = 1;
else w[i] = 0;
}
if(ask(w) == dist) {
RE(i,n) onPath[i] = 0;
for(int i:rem) onPath[i] = 1;
}
ones = 0;
RE(i,n) if(onPath[i]) ones++;
}
int w=0;
RE(i,n) if(onPath[i]) w = i;
int s = getS(w);
int t = getS(s);
answer(s, t);
}
