#include <bits/stdc++.h>
#include "highway.h"
using namespace std;
const int MAXN = 90000;
const int MAXM = 130000;
int n, m, tIn[MAXN], timer, h[MAXN], cnt[MAXN];
vector<int> u, v, adj[MAXN];
long long allA;
bool mark[MAXM];
void BuildTree(int s) {
timer = 0;
for(int i = 0; i < n; i++){
h[i] = -1;
cnt[i] = 0;
}
queue<int> qu;
h[s] = 0;
tIn[s] = timer++;
qu.push(s);
while (!qu.empty()) {
int u = qu.front();
qu.pop();
cnt[h[u]]++;
for(int ind : adj[u]) {
if (mark[ind])
continue;
int v = ::u[ind] ^ ::v[ind] ^ u;
if (h[v] == -1) {
h[v] = h[u] + 1;
tIn[v] = timer++;
qu.push(v);
}
}
}
for(int i = 1; i < n; i++)
cnt[i] += cnt[i - 1];
}
long long MyAsk(int l, int r) {
vector<int> w(m);
for(int i = 0; i < m; i++)
if (mark[i] || (l <= tIn[u[i]] && tIn[u[i]] <= r) || (l <= tIn[v[i]] && tIn[v[i]] <= r))
w[i] = 1;
else
w[i] = 0;
return ask(w);
}
int Find_city(int l, int r) {
//assert(timer == n);
int res = -1;
while (l <= r) {
int mid = (l + r) >> 1;
if (MyAsk(mid, n - 1) != allA) {
res = mid;
l = mid + 1;
} else {
r = mid - 1;
}
}
for(int i = 0; i < m; i++)
if ((res < tIn[u[i]] && tIn[u[i]] <= n - 1) || (res < tIn[v[i]] && tIn[v[i]] <= n - 1))
mark[i] = 1;
for(int i = 0; i < n; i++)
if (tIn[i] == res)
return i;
assert(0);
}
void find_pair(int _n, vector<int> _u, vector<int> _v, int a, int b) {
n = _n;
u = _u;
v = _v;
m = u.size();
for(int i = 0; i < m; i++) {
adj[u[i]].push_back(i);
adj[v[i]].push_back(i);
}
iota(tIn, tIn + n, 0);
timer = n;
allA = MyAsk(-1, -1);
int dist = allA / a;
int root = Find_city(0, n - 1);
BuildTree(root);
int s = Find_city(0, cnt[dist] - 1);
BuildTree(s);
int t = Find_city(0, cnt[dist] - 1);
answer(s, t);
}
