#include <bits/stdc++.h>
using namespace std;
#include "highway.h"
const int N = 90000;
int order[N], where[N], color[N], dist[2][N], ans[2], n;
vector<int> adj[N];
void bfs(int s, int *level) {
fill(level, level + n, -1);
level[s] = 0;
queue<int> que;
que.push(s);
while (!que.empty()) {
int u = que.front();
que.pop();
for (auto c : adj[u]) {
if (level[c] == -1) {
level[c] = level[u] + 1;
que.push(c);
}
}
}
}
void find_pair(int n, vector<int> u, vector<int> v, int a, int b) {
::n = n;
int m = u.size();
int d = ask(vector<int>(m));
for (int i = 0; i < m; ++i) {
adj[u[i]].push_back(v[i]);
adj[v[i]].push_back(u[i]);
}
int low = 0, high = m - 1;
while (low < high) {
int mid = (low + high) / 2;
vector<int> traffic(m);
for (int i = 0; i <= mid; ++i) {
traffic[i] = true;
}
if (ask(traffic) > d) {
high = mid;
} else {
low = mid + 1;
}
}
int bridge = low;
bfs(u[bridge], dist[0]);
bfs(v[bridge], dist[1]);
for (int i = 0; i < n; ++i) {
if (dist[0][i] < dist[1][i]) {
color[i] = 0;
} else {
color[i] = 1;
}
}
for (int k = 0; k < 2; ++k) {
int nk = 0;
for (int i = 0; i < n; ++i) {
if (color[i] == k) {
order[nk++] = i;
}
}
sort(order, order + nk, [&](int a, int b) {
return dist[k][a] < dist[k][b];
});
for (int i = 0; i < nk; ++i) {
where[order[i]] = i;
}
low = 0, high = nk - 1;
while (low < high) {
int mid = (low + high) / 2;
vector<int> traffic(m);
for (int i = 0; i < m; ++i) {
if (i == bridge) {
traffic[i] = false;
} else if (color[u[i]] != color[v[i]]) {
traffic[i] = true;
} else if (dist[color[u[i]]][u[i]] == dist[color[v[i]]][v[i]]) {
traffic[i] = true;
} else if (color[u[i]] != k) {
traffic[i] = false;
} else if (max(where[u[i]], where[v[i]]) <= mid) {
traffic[i] = false;
} else {
traffic[i] = true;
}
}
if (ask(traffic) > d) {
low = mid + 1;
} else {
high = mid;
}
}
ans[k] = order[low];
}
answer(ans[0], ans[1]);
}
