#include "highway.h"
//#include "grader.cpp"
#include <bits/stdc++.h>
#define pii pair<int, int>
#define fr first
#define sc second
#define szof(s) (int)s.size()
#define all(s) s.begin(), s.end()
#define mk make_pair
#define pb push_back
#define ll long long
using namespace std;
const int MAXN = 130005;
const ll INF = 0x3f3f3f3f3f3f3f3f;
int n, m;
vector <pair<int, int>> G[MAXN]; // обычный граф
vector <pair<int, int>> tree[MAXN]; // дерево
int edge[MAXN][2];
bool used[MAXN];
ll costa, costb;
ll diametr;
ll min_path, max_path;
int ROOT, SUB_S;
vector <int> bfs_edges; // already sorted by id
ll get_min_path() {
vector <int> w(m);
for (int i = 0; i < m; i++) {
w[i] = 0;
}
ll cur_cost = ask(w);
return cur_cost;
}
int find_root() {
vector <int> w(m);
for (int i = 0; i < m; i++) {
w[i] = 0;
}
w[0] = 1;
ll cur_cost;
int l = -1, r = m - 1;
while (r - l > 1) {
int mid = (l + r) >> 1;
for (int i = 0; i < m; i++) {
w[i] = 0;
}
for (int i = 0; i <= mid; i++) {
w[i] = 1;
}
cur_cost = ask(w);
if (cur_cost == min_path) {
l = mid;
} else {
r = mid;
}
}
return edge[r][0];
}
void create_tree(int root) {
bfs_edges.clear();
memset(used, 0, sizeof(used));
for (int i = 0; i < MAXN; i++) {
tree[i].clear();
}
// найти ребро на пути S -> T
queue <int> q;
vector <int> dist(MAXN, -1);
dist[root] = 0;
q.push(root);
ROOT = root;
while (!q.empty()) {
int v = q.front();
q.pop();
for (pii to : G[v]) {
if (dist[to.fr] == -1) {
used[to.sc] = true;
bfs_edges.pb(to.sc);
tree[v].pb({to.fr, to.sc});
tree[to.fr].pb({v, to.sc});
dist[to.fr] = dist[v] + 1;
q.push(to.fr);
}
}
}
}
int d[MAXN];
void calc(int v, int par, int len) {
d[v] = len;
for (pii to : tree[v]) {
if (to.fr != par) {
calc(to.fr, v, len + 1);
}
}
}
int find_ans() {
int l = 0, r = szof(bfs_edges);
vector <int> w(m);
while (r - l > 1) {
int mid = (l + r) >> 1;
for (int i = 0; i < m; i++) {
w[i] = 1;
}
for (int el : bfs_edges) {
w[el] = 0;
}
for (int i = mid; i < szof(bfs_edges); i++) {
w[bfs_edges[i]] = 1;
}
ll cur_cost = ask(w);
if (cur_cost == min_path) {
r = mid;
} else {
l = mid;
}
}
int need_edge = bfs_edges[l];
int px = edge[need_edge][0], py = edge[need_edge][1];
return (d[px] > d[py] ? px : py);
}
void find_pair(int N, vector<int> U, vector<int> V, int AA, int BB) {
m = szof(U);
n = N;
costa = AA;
costb = BB;
min_path = get_min_path(); // 1 q
diametr = min_path / costa;
max_path = diametr * costb;
for (int i = 0; i < m; i++) {
int x, y;
x = U[i];
y = V[i];
edge[i][0] = x;
edge[i][1] = y;
G[x].pb({y, i});
G[y].pb({x, i});
}
int root = find_root();
create_tree(root); // log(n)
calc(root, -1, 0);
int s = find_ans(); // log(n)
create_tree(s);
calc(s, -1, 0);
int t = find_ans();
answer(s, t);
}
