#include "highway.h"
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
using namespace std;
const int NMAX = 1e6 + 1;
vector <vector <int> > g(NMAX);
int D[NMAX][2];
vector <int> p(NMAX, -1);
int n;
ll a, b;
int d[NMAX][2];
ll sz1, sz2 = 0;
map<pii, bool> used1;
vector <bool> used(NMAX);
void bfs(int x, int y){
queue <int> q;
q.push(x);
//cout << x << y;
used1[{x, y}] = used1[{y, x}] = true;
for(int i = 0; i < n; i++){
D[i][0] = D[i][1] = 1e9;
d[i][0] = d[i][1] = -1;
}
D[x][0] = 0;
q.push(x);
while(!q.empty()){
int v = q.front();
// cout << v << ' ';
q.pop();
for(int to : g[v]){
if(D[to][0] > D[v][0] + 1){
D[to][0] = D[v][0] + 1;
q.push(to);
}
}
}
D[y][1] = 0;
q.push(y);
while(!q.empty()){
int v = q.front();
q.pop();
for(int to : g[v]){
if(D[to][1] > D[v][1] + 1){
D[to][1] = D[v][1] + 1;
q.push(to);
}
}
}
q.push(x);
int cnt = 1;
d[x][0] = 0;
while(!q.empty()){
int v = q.front();
q.pop();
for(int to : g[v]){
if(D[to][0] < D[to][1]){
if(d[to][0] == -1) {d[to][0] = cnt++, sz1++, used1[{v, to}] = used1[{to, v}] = true, q.push(to); }
}
}
}
q.push(y);
cnt = 1;
d[y][1] = 0;
while(!q.empty()){
int v = q.front(); q.pop();
for(int to : g[v]){
if(D[to][1] <= D[to][0]){
if(d[to][1] == -1) d[to][1] = cnt++, sz2++, used1[{v, to}] = used1[{to, v}] = true, q.push(to);
}
}
}
}
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
n = N;
int m = U.size();
for(int i = 0; i < m; i++){
g[U[i]].pb(V[i]);
g[V[i]].pb(U[i]);
}
ll a = A, b = B;
vector <int> vec;
vec.resize(m);
const vector <int> v = vec;
ll mn = ask(v);
int l = -1, r = n;
while(l + 1 < r){
int mid = (l + r) / 2;
vector <int> xx;
for(int i = 0; i < m; i++){
if(i <= mid) xx.pb(0);
else xx.pb(1);
}
const vector <int> vv = xx;
ll x = ask(vv);
if(x == mn) r = mid;
else l = mid;
}
// cout << r << "\n";
int x = U[r], y = V[r];
bfs(x, y);
for(int i = 0; i < m; i++){
if(used1[{U[i], V[i]}]) used[i] = true;
}
l = -1, r = sz1 + 1;
while(l + 1 < r){
int mid = (l + r) / 2;
vector <int> xx;
for(int i = 0; i < m; i++){
int u = U[i], v = V[i];
if(!used[i]) xx.pb(1);
else{
if(d[u][0] <= mid && d[v][0] <= mid) xx.pb(0);
else xx.pb(1);
}
}
const vector <int> vv = xx;
ll x = ask(vv);
if(x == mn) r = mid;
else l = mid;
}
int s;
for(int i = 0; i < n; i++) if(d[i][0] == r) {s = i; break;}
//cout << s << "\n";
l = -1, r = sz2;
while(l + 1 < r){
int mid = (l + r) / 2;
vector <int> xx;
for(int i = 0; i < m; i++){
int u = U[i], v = V[i];
if(used[i]) xx.pb(1);
else{
if(d[u][1] <= mid && d[v][1] <= mid) xx.pb(0);
else xx.pb(1);
}
}
const vector <int> vv = xx;
ll x = ask(vv);
if(x == mn) r = mid;
else l = mid;
}
//cout << r;
int t;
for(int i = 0; i < n; i++) if(d[i][1] == r) {t = i; break;}
answer(s, t);
}
