#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
template<class T, class U>
void ckmin(T &a, U b)
{
if (a > b) a = b;
}
template<class T, class U>
void ckmax(T &a, U b)
{
if (a < b) a = b;
}
#define MP make_pair
#define PB push_back
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define FOR(i, a, b) for (auto i = (a); i < (b); i++)
#define FORD(i, a, b) for (auto i = (a) - 1; i >= (b); i--)
#define SZ(x) ((int) ((x).size()))
#define ALL(x) (x).begin(), (x).end()
#define MAXN 90013
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef vector<pll> vpl;
int N, T, U, V, M;
ll A, B, D;
vi edge[MAXN];
unordered_map<int, int> eid[MAXN];
int st[MAXN], rev[MAXN];
int parent[MAXN];
vi qry;
void dfs(int u, int p)
{
st[u] = T; rev[T] = u;
T++;
for (int v : edge[u])
{
if (v == p) continue;
parent[v] = u;
dfs(v, u);
}
}
void find_pair(int n, vi u, vi v, int a, int b)
{
N = n; A = a; B = b; M = SZ(u); int lo, hi;
FOR(i, 0, M)
{
edge[u[i]].PB(v[i]);
edge[v[i]].PB(u[i]);
eid[u[i]][v[i]] = i;
eid[v[i]][u[i]] = i;
}
qry.resize(M); D = ask(qry);
T = 0;
dfs(0, N);
//binary serach on euler tour.
lo = 0; hi = N;
while(hi > lo)
{
int mid = (hi + lo) >> 1;
FOR(i, 0, M) qry[i] = 0;
FOR(i, mid + 1, M)
{
int u = rev[i];
qry[eid[u][parent[u]]] = 1;
}
if (ask(qry) == D) hi = mid;
else lo = mid + 1;
}
U = rev[lo];
T = 0;
dfs(0, U);
lo = 0; hi = N;
while(hi > lo)
{
int mid = (hi + lo) >> 1;
FOR(i, 0, M) qry[i] = 0;
FOR(i, mid + 1, M)
{
int u = rev[i];
qry[eid[u][parent[u]]] = 1;
}
if (ask(qry) == D) hi = mid;
else lo = mid + 1;
}
V = rev[lo];
answer(U, V);
//binary search on euler tour twice.
}
