#include <bits/stdc++.h>
#include "highway.h"
using namespace std;
typedef long long ll;
vector <int> G[101010], X, Y;
queue <int> Q;
int D1[101010], N1[101010], P1[101010];
int D2[101010], N2[101010], P2[101010];
int cnt;
void bfs(int p, int *D, int *N, int *P)
{
cnt = 0; Q.push(p);
N[p] = ++cnt;
for(; !Q.empty(); ){
p = Q.front(); Q.pop();
for(int &t: G[p]){
if(!N[t]){
P[t] = p; D[t] = D[p] + 1;
N[t] = ++cnt;
Q.push(t);
}
}
}
}
void find_pair(int n, vector <int> U, vector <int> V, int a, int b)
{
int m = U.size();
vector <int> W(m, 0);
int i, k, t, x, u, v, s, e;
for(i=0; i<m; i++){
G[U[i]].push_back(V[i]);
G[V[i]].push_back(U[i]);
}
k = ask(W) / a;
for(s=0, e=m-1; s<=e; ){
for(i=0; i<m; i++){
if(i <= (s + e >> 1)) W[i] = 1;
else W[i] = 0;
}
if(ask(W) != (ll)a * k) e = (s + e >> 1) - 1;
else s = (s + e >> 1) + 1;
}
t = e + 1;
bfs(U[t], D1, N1, P1);
bfs(V[t], D2, N2, P2);
for(i=0; i<n; i++){
if(D1[i] < D2[i]) X.push_back(i);
else if(D1[i] > D2[i]) Y.push_back(i);
}
sort(X.begin(), X.end(), [&](int &a, int &b){
return N1[a] < N1[b];
});
sort(Y.begin(), Y.end(), [&](int &a, int &b){
return N2[a] < N2[b];
});
for(s=0, e=X.size()-1; s<=e; ){
x = N1[X[s + e >> 1]];
for(i=0; i<m; i++){
if(i == t) W[i] = 0;
else if(D1[U[i]] < D2[U[i]] && D1[V[i]] < D2[V[i]]){
if(P1[U[i]] != V[i] && P1[V[i]] != U[i]) W[i] = 1;
else if(max(N1[U[i]], N1[V[i]]) > x) W[i] = 1;
else W[i] = 0;
}
else if(D1[U[i]] > D2[U[i]] && D1[V[i]] > D2[V[i]]) W[i] = 0;
else W[i] = 1;
}
if(ask(W) != (ll)a * k) s = (s + e >> 1) + 1;
else e = (s + e >> 1) - 1;
}
u = X[e + 1];
for(s=0, e=Y.size()-1; s<=e; ){
x = N2[Y[s + e >> 1]];
for(i=0; i<m; i++){
if(i == t) W[i] = 0;
else if(D2[U[i]] < D1[U[i]] && D2[V[i]] < D1[V[i]]){
if(P2[U[i]] != V[i] && P2[V[i]] != U[i]) W[i] = 1;
else if(max(N2[U[i]], N2[V[i]]) > x) W[i] = 1;
else W[i] = 0;
}
else if(D2[U[i]] > D1[U[i]] && D2[V[i]] > D1[V[i]]) W[i] = 0;
else W[i] = 1;
}
if(ask(W) != (ll)a * k) s = (s + e >> 1) + 1;
else e = (s + e >> 1) - 1;
}
v = Y[e + 1];
answer(u, v);
}
