#include <bits/stdc++.h>
#include "highway.h"
using namespace std;
#define Fi first
#define Se second
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define szz(x) (int)(x).size()
#define rep(i, n) for(int i=0;i<(n);i++)
typedef tuple<int, int, int> t3;
vector <int> EV;
vector <pii> E[100010];
int dv[2][100010], chk[100010];
void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
int M = szz(U);
rep(i, M) E[U[i]].pb({V[i], i}), E[V[i]].pb({U[i], i});
EV.resize(M);
ll dist = ask(EV);
int low = 0, high = M - 1;
while(low < high) {
int mid = (low + high) >> 1;
rep(i, M) EV[i] = (low <= i && i <= mid);
if(ask(EV) != dist) high = mid;
else low = mid + 1;
}
int P = U[low], Q = V[low], tl = low;
rep(u, 2) {
int st = (u ? Q : P);
vector <int> q; q.pb(st);
rep(i, N) dv[u][i] = -1;
dv[u][st] = 0;
rep(i, szz(q)) {
int t = q[i];
for(auto [e, _] : E[t]) if(dv[u][e] == -1) {
dv[u][e] = dv[u][t] + 1;
q.pb(e);
}
}
}
auto Find = [&](int P, vector <int> &C, int dis[]) {
sort(all(C), [&](int x, int y) { return dis[x] < dis[y]; });
int low = 0, high = szz(C) - 1;
while(low < high) {
int mid = (low + high) >> 1;
rep(i, M) EV[i] = (i != tl && chk[U[i]] != chk[V[i]]);
for(int i=mid+1;i<szz(C);i++) {
int x = C[i];
for(auto [e, id] : E[x]) {
if(dis[e] + 1 == dis[x]) EV[id] = 1;
}
}
if(ask(EV) != dist) low = mid + 1;
else high = mid;
}
return C[low];
};
vector <int> R[2];
rep(i, N) {
if(dv[0][i] < dv[1][i]) R[0].pb(i), chk[i] = 0;
else if(dv[0][i] > dv[1][i]) R[1].pb(i), chk[i] = 1;
else chk[i] = 2;
}
answer(Find(P, R[0], dv[0]), Find(Q, R[1], dv[1]));
}
