#include "highway.h"
#include <cstdio>
#include <algorithm>
#define N_ 151000
using namespace std;
int n, m, Q[N_], head, tail, par[N_], vis[N_], pN[N_], vv[N_];
vector<int>T, E[N_];
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
int i;
n = N;
m = U.size();
T.resize(m);
for (i = 0; i < m; i++) {
T[i] = 0;
E[U[i]].push_back(V[i]);
E[V[i]].push_back(U[i]);
}
long long L = ask(T);
int b = 0, e = n - 2, mid, r = n - 1;
while (b <= e) {
mid = (b + e) >> 1;
if (e - b > 60000)mid = 60000;
for (i = 0; i < m; i++) {
if (U[i] > mid || V[i] > mid)T[i] = 1;
else T[i] = 0;
}
if (ask(T) == L)r = mid, e = mid - 1;
else b = mid + 1;
}
int root = r;
Q[++tail] = root, vis[root] = 1;
par[root] = -1;
while (head < tail) {
int x = Q[++head];
for (auto &y : E[x]) {
if (!vis[y]) {
vis[y] = 1;
Q[++tail] = y;
par[y] = x;
}
}
}
for (i = 0; i < m; i++) {
if (par[U[i]] == V[i])pN[U[i]] = i;
if (par[V[i]] == U[i])pN[V[i]] = i;
}
b = 1, e = tail - 1, r = tail;
while (b <= e) {
mid = (b + e) >> 1;
if (e - b > 60000)mid = 60000;
for (i = 0; i < m; i++)T[i] = 1;
for (i = 2; i <= mid; i++) T[pN[Q[i]]] = 0;
if (ask(T) == L)r = mid, e = mid - 1;
else b = mid + 1;
}
int ed = Q[r];
int tp = ed;
while (tp != root) {
vv[pN[tp]] = 1;
tp = par[tp];
}
b = 1, e = r - 1;
while (b <= e) {
mid = (b + e) >> 1;
for (i = 0; i < m; i++) {
if(!vv[i])T[i] = 1;
else T[i] = 0;
}
for (i = 2; i <= mid; i++) T[pN[Q[i]]] = 0;
if (ask(T) == L)r = mid, e = mid - 1;
else b = mid + 1;
}
int st = Q[r];
answer(st, ed);
}
