#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
#define debug(s) cout << #s << " = " << s << endl
typedef long long ll;
typedef pair<int, int> ii;
const int maxn = 500005;
namespace {
vector<int> L, R, g[maxn], t[maxn], vis, lvl, pe, wot, where;
ll pathLen, A, B;
int S, T, tym = 0, n, m;
}
void bfs(int root) {
queue<int> Q;
Q.emplace(root);
lvl[root] = 0;
pe[root] = -1, vis[root] = 1;
while(Q.size()) {
int u = Q.front();
Q.pop();
for(int i : g[u]) {
int v = L[i] ^ R[i] ^ u;
if(!vis[v]) {
vis[v] = 1;
Q.emplace(v);
lvl[v] = lvl[u] + 1;
pe[v] = i;
t[u].emplace_back(i);
t[v].emplace_back(i);
}
}
}
}
void dfs(int u) {
vis[u] = 1;
wot[tym] = u;
where[u] = tym++;
for(int i : t[u]) {
int v = L[i] ^ R[i] ^ u;
if(!vis[v]) {
pe[v] = i;
dfs(v);
}
}
}
void find_pair(int _N, std::vector<int> _U, std::vector<int> _V, int _A, int _B) {
n = _N, L = _U, R = _V, A = _A, B = _B, m = _U.size();
vis.assign(n, 0), lvl.assign(n, 0), pe.assign(n, 0), wot.assign(n, 0), where.assign(n, 0);
for(int i = 0; i < m; i++) {
g[L[i]].emplace_back(i);
g[R[i]].emplace_back(i);
// cout << i << " ----> " << L[i] << ' ' << R[i] << endl;
}
{
vector<int> w(m);
pathLen = ask(w) / A;
// debug(pathLen);
}
int root;
{
int lo = 0, hi = m - 1, mid, ret = -1;
while(lo <= hi) {
mid = lo + hi >> 1;
vector<int> w(m);
for(int i = 0; i <= mid; i++) {
w[i] = 1;
}
if(ask(w) != A * pathLen) {
ret = mid;
hi = mid - 1;
} else {
lo = mid + 1;
}
}
root = ret == -1 ? -1 : L[ret];
}
// debug(root);
bfs(root);
fill(vis.begin(), vis.end(), 0);
pe[root] = -1;
dfs(root);
// for(int b : wot) cout << b << ' '; cout << endl;
// for(int b : pe) cout << b << ' '; cout << endl;
S = T = -1;
{
int lo = 0, hi = n - 1, mid;
while(lo <= hi) {
mid = lo + hi >> 1;
vector<int> w(m, 1);
for(int i = 0; i <= mid; i++) {
w[pe[wot[i]]] = 0;
}
if(ask(w) == A * pathLen) {
S = wot[mid];
hi = mid - 1;
} else {
lo = mid + 1;
}
}
}
tym = 0;
pe[S] = -1;
fill(vis.begin(), vis.end(), 0);
dfs(S);
{
int lo = 0, hi = n - 1, mid;
while(lo <= hi) {
mid = lo + hi >> 1;
vector<int> w(m, 1);
for(int i = 0; i <= mid; i++) {
w[pe[wot[i]]] = 0;
}
// int u = S;
// while(pe[u] != -1) {
// w[pe[u]] = 1;
// u = u ^ L[pe[u]] ^ R[pe[u]];
// }
// for(int i = 0; i < m; i++) cout << i << ' '; cout << endl;
// for(int b : w) cout << b << ' '; cout << endl;
// debug(ask(w));
if(ask(w) == A * pathLen) {
T = wot[mid];
hi = mid - 1;
} else {
lo = mid + 1;
}
}
}
// debug(S), debug(T);
answer(S, T);
}
