#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 9e4+5;
int M, X, Y, L, R, mid, dist[2][MAXN];
ll D, E;
bool act[MAXN];
vector <int> B, S, adj[MAXN];
queue <int> Q;
void bfs(int s,int t) {
Q.push(s);
dist[t][s] = 1;
while (!Q.empty()) {
int x = Q.front();
Q.pop();
for (int y : adj[x]) {
if (!dist[t][y]) {
dist[t][y] = dist[t][x]+1;
Q.push(y);
}
}
}
}
bool cmp(int x,int y) {
return dist[0][x] > dist[0][y];
}
void find_pair(int N,vector<int> U,vector<int> V,int A,int b) {
M = U.size();
for (int i=0;i<M;i++) {
B.push_back(0);
}
D = ask(B);
L = 0;
R = M-1;
while (L < R) {
mid = (L+R)>>1;
for (int i=0;i<=mid;i++) {
B[i] = 0;
}
for (int i=mid+1;i<M;i++) {
B[i] = 1;
}
E = ask(B);
if (E == D) {
R = mid;
}
else {
L = mid+1;
}
}
X = U[L];
Y = V[L];
for (int i=0;i<M;i++) {
adj[U[i]].push_back(V[i]);
adj[V[i]].push_back(U[i]);
}
bfs(X,0);
bfs(Y,1);
for (int i=0;i<N;i++) {
if (dist[0][i] < dist[1][i] && dist[0][i] <= D/A) {
S.push_back(i);
}
}
sort(S.begin(),S.end(),cmp);
L = 0;
R = S.size()-1;
while (L < R) {
mid = (L+R)>>1;
for (int i=0;i<N;i++) {
act[i] = 0;
}
for (int i=0;i<=mid;i++) {
act[S[i]] = 1;
}
for (int i=0;i<M;i++) {
B[i] = act[U[i]]||act[V[i]];
}
E = ask(B);
if (E == D) {
L = mid+1;
}
else {
R = mid;
}
}
X = S[L];
S.clear();
for (int i=0;i<N;i++) {
if (dist[0][i] > dist[1][i] && dist[0][X]+dist[1][i]-1 == D/A) {
S.push_back(i);
}
}
L = 0;
R = S.size()-1;
while (L < R) {
mid = (L+R)>>1;
for (int i=0;i<N;i++) {
act[i] = 0;
}
for (int i=0;i<=mid;i++) {
act[S[i]] = 1;
}
for (int i=0;i<M;i++) {
B[i] = act[U[i]]||act[V[i]];
}
E = ask(B);
if (E == D) {
L = mid+1;
}
else {
R = mid;
}
}
Y = S[L];
answer(X, Y);
}
