#include <bits/stdc++.h>
#include "highway.h"
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define pb push_back
#define FIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
using namespace std;
typedef long long ll;
typedef pair <int, int> pii;
const int maxN = 90007;
ll odis;
int bio[maxN], dub[maxN];
vector <pii> adj[maxN];
void dfs(int x) {
bio[x] = 1;
for (auto y : adj[x]) {
if (bio[y.F]) continue;
dub[y.F] = dub[x]+1;
dfs(y.F);
}
}
void find_pair(int n, vector <int> u, vector <int> v, int a, int b) {
int m = u.size();
vector <int> tmp(m, 0);
odis = ask(tmp);
for (int i = 0; i < m; i++) {
adj[u[i]].pb({v[i], i});
adj[v[i]].pb({u[i], i});
}
dfs(0);
vector <int> e;
for (int i = 0; i < m; i++) e.pb(i);
sort(all(e), [&](int x, int y) {return max(dub[u[x]], dub[v[x]]) > max(dub[u[y]], dub[v[y]]);});
int lo = 0, hi = m-1;
while (lo < hi) {
int mid = (lo + hi) / 2;
vector <int> ed(m, 0);
for (int i = 0; i <= mid; i++) ed[e[i]] = 1;
if (odis != ask(ed)) hi = mid;
else lo = mid+1;
}
int nx = u[e[lo]], ny = v[e[lo]];
auto bfs = [&](vector <int> vv) {
queue <int> q;
memset(bio, -1, sizeof bio);
for (auto x : vv) {
bio[x] = 0;
q.push(x);
}
vector <int> tmp(m, 1);
while (!q.empty()) {
int x = q.front(); q.pop();
for (auto y : adj[x]) {
if (bio[y.F] != -1) continue;
bio[y.F] = bio[x] + 1;
tmp[y.S] = 0;
q.push(y.F);
}
}
vector <int> e;
for (int i = 0; i < m; i++) e.pb(i);
sort(all(e), [&](int x, int y){return max(bio[v[x]], bio[u[x]]) < max(bio[v[y]], bio[u[y]]);});
lo = 0, hi = m-1;
while (lo < hi) {
int mid = (lo + hi) / 2;
vector <int> ed; ed = tmp;
for (int i = 0; i <= mid; i++) ed[e[i]] = 1;
if (odis/a*b != ask(ed)) lo = mid+1;
else hi = mid;
}
int xx = u[e[lo]];
if (bio[v[e[lo]]] > bio[xx]) xx = v[e[lo]];
return xx;
};
int z = bfs({nx, ny});
int w = bfs({z});
answer(z, w);
}
