#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
#define I signed
#define int long long
vector<signed> E, P;
vector<vector<pair<int,int>>> adj;
void dfs1(int v, int p) {
for(auto &[u, i]: adj[v]) {
if (u == p) continue;
E[i] = 1;
dfs1(u, v);
}
}
void dfs2(int v, int p, int d, int t) {
if (d == t) P.push_back(v);
for(auto &[u, i]: adj[v]) {
if (u == p) continue;
dfs2(u, v, d+1, t);
}
}
void find_pair(I N, vector<I> U, vector<I> V, I A, I B) {
int M = U.size();
E.assign(M, 0), adj.resize(N);
for(int i = 0; i < M; i++) adj[U[i]].push_back({V[i], i}), adj[V[i]].push_back({U[i], i});
int S, T;
int emptc = ask(E);
int l = 0, r = M;
while(l < r - 1) {
int m = (l + r) / 2;
E.assign(M, 0);
for(int i = 0; i < m; i++) E[i] = 1;
if (ask(E) != emptc) r = m;
else l = m;
}
int u = U[l], v = V[l];
E.assign(M, 0);
dfs1(u, v);
int nume = (ask(E) - emptc) / (B-A);
dfs2(u, v, 0, nume);
l = 0, r = P.size();
while(l < r - 1) {
int m = (l + r) / 2;
E.assign(M, 0);
for(int i = 0; i < m; i++) {
for(auto &[a, x]: adj[P[i]]) E[x] = 1;
}
if (ask(E) != emptc) r = m;
else l = m;
}
S = P[l];
P.clear();
E.assign(M, 0);
dfs1(v, u);
nume = (ask(E) - emptc) / (B-A);
dfs2(v, u, 0, nume);
l = 0, r = P.size();
while(l < r - 1) {
int m = (l + r) / 2;
E.assign(M, 0);
for(int i = 0; i < m; i++) {
for(auto &[a, x]: adj[P[i]]) E[x] = 1;
}
if (ask(E) != emptc) r = m;
else l = m;
}
T = P[l];
answer(S, T);
}
