//Egrader.cpp
#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
#define all(x) begin(x), end(x)
#define sz(x) ((int) (x).size())
using ll = long long;
using ld = long double;
const int N = 9e4 + 10, M = 1.3e5 + 10, INF = 0x3f3f3f3f;
struct Edge {
int v, i;
};
vector<Edge> g[N];
int dist[N];
int order[N], by_order[N];
void find_pair(int n, vector<int> us, vector<int> vs, int a, int b) {
int m = sz(us);
for (int i = 0; i < m; ++i) {
g[us[i]].push_back({vs[i], i});
g[vs[i]].push_back({us[i], i});
}
int l = 1, r = n;
ll baseline = ask(vector(m, 0));
while (r - l > 1) {
int mid = (l + r) / 2;
vector w(m, 0);
for (int i = 0; i < m; ++i) {
if (max(us[i], vs[i]) >= mid) {
w[i] = 1;
}
}
if (baseline == ask(w)) {
r = mid;
} else {
l = mid;
}
}
int bound = r;
queue<int> bfs;
bfs.push(l);
int cnt = 0;
fill(all(dist), +INF);
dist[l] = 0;
while (sz(bfs)) {
int u = bfs.front();
// cout << u << endl;
bfs.pop();
by_order[cnt] = u;
order[u] = cnt++;
for (auto [v, _] : g[u]) {
if (v < bound && dist[v] > dist[u] + 1) {
dist[v] = dist[u] + 1;
bfs.push(v);
}
}
}
l = 1, r = cnt;
while (r - l > 1) {
int mid = (l + r) / 2;
vector w(m, 0);
for (int i = 0; i < m; ++i) {
if (max(us[i], vs[i]) >= bound || max(order[us[i]], order[vs[i]]) >= mid) {
w[i] = 1;
}
}
if (baseline == ask(w)) {
r = mid;
} else {
l = mid;
}
}
int root = by_order[l];
// cout << l << " " << r << endl;
// cout << by_order[0] << " " << by_order[1] << " " << by_order[2] << endl;
{
bfs.push(root);
cnt = 0;
fill(all(dist), +INF);
dist[root] = 0;
while (sz(bfs)) {
int u = bfs.front();
bfs.pop();
by_order[cnt] = u;
order[u] = cnt++;
for (auto [v, _] : g[u]) {
if (dist[v] > dist[u] + 1) {
dist[v] = dist[u] + 1;
bfs.push(v);
}
}
}
l = 0, r = cnt;
while (r - l > 1) {
int mid = (l + r) / 2;
vector w(m, 0);
for (int i = 0; i < m; ++i) {
if (max(order[us[i]], order[vs[i]]) >= mid) {
w[i] = 1;
}
}
if (baseline == ask(w)) {
r = mid;
} else {
l = mid;
}
}
answer(by_order[l], root);
}
}
