#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;
vector <int> bfs_edges[3]; // already sorted by id
map <pii, int> id;
//int N, M, A, B, S, T;
//vector <int> U, V;
//vector <vector<pii>> graph;
//long long ask(const std::vector<int> &w) {
//std::vector<bool> visited(N, false);
//std::vector<long long> current_dist(N, INF);
//std::queue<int> qa, qb;
//qa.push(S);
//current_dist[S] = 0;
//while (!qa.empty() || !qb.empty()) {
//int v;
//if (qb.empty() ||
//(!qa.empty() && current_dist[qa.front()] <= current_dist[qb.front()])) {
//v = qa.front();
//qa.pop();
//} else {
//v = qb.front();
//qb.pop();
//}
//if (visited[v]) {
//continue;
//}
//visited[v] = true;
//long long d = current_dist[v];
//if (v == T) {
//return d;
//}
//for (auto e : graph[v]) {
//int vv = e.first;
//int ei = e.second;
//if (!visited[vv]) {
//if (w[ei] == 0) {
//if (current_dist[vv] > d + A) {
//current_dist[vv] = d + A;
//qa.push(vv);
//}
//} else {
//if (current_dist[vv] > d + B) {
//current_dist[vv] = d + B;
//qb.push(vv);
//}
//}
//}
//}
//}
//return -1;
//}
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;
}
}
ROOT = edge[r][0];
SUB_S = edge[r][1];
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);
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];
int tin[MAXN];
int tout[MAXN];
int tiktak = 0;
void calc(int v, int par, int len) {
tin[v] = ++tiktak;
d[v] = len;
for (pii to : tree[v]) {
if (to.fr != par) {
calc(to.fr, v, len + 1);
}
}
tout[v] = tiktak;
}
bool father(int a, int b) {
return tin[a] <= tin[b] && tout[b] <= tout[a];
}
vector <int> subtree[3];
void dfs(int v, int par) {
if (father(SUB_S, v)) {
subtree[1].pb(v);
} else {
subtree[2].pb(v);
}
for (pii to : tree[v]) {
if (to.fr != par) {
dfs(to.fr, v);
}
}
}
int find_ans(int cur_root, vector <int> cur_bfs_edges) {
if (cur_bfs_edges.empty()) {
return cur_root;
}
int l = 0, r = szof(cur_bfs_edges);
vector <int> w(m, 1);
// check for not root
for (int el : BFS_EDGES) {
w[el] = 0;
}
for (int el : cur_bfs_edges) {
w[el] = 1;
}
ll wtf_cost = ask(w);
if (wtf_cost == min_path) {
//cout << "wtf: " << cur_root << endl;
return cur_root;
}
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(cur_bfs_edges); i++) {
w[cur_bfs_edges[i]] = 1;
}
ll cur_cost = ask(w);
if (cur_cost == min_path) {
r = mid;
} else {
l = mid;
}
}
int x = edge[cur_bfs_edges[l]][0];
int y = edge[cur_bfs_edges[l]][1];
//cout << "x y: " << x << " " << y << endl;
//cout << "d[x] d[y]: " << d[x] << " " << d[y] << endl;
return (d[x] > d[y] ? x : y);
}
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];
id[{x, y}] = i;
id[{y, x}] = i;
edge[i][0] = x;
edge[i][1] = y;
G[x].pb({y, i});
G[y].pb({x, i});
}
int s, t;
int root = find_root(); // log(n)
//cout << "ROOTIK AND SUB_S: " << ROOT << " " << SUB_S << endl;
create_tree(root);
calc(root, -1, 0);
dfs(root, -1);
sort(all(subtree[1]));
sort(all(subtree[2]));
auto exist = [&](vector <int> &vec, int x) {
bool ok = binary_search(all(vec), x);
return ok;
};
for (int el : BFS_EDGES) {
int x = edge[el][0];
int y = edge[el][1];
if ((x == ROOT && y == SUB_S) || (x == SUB_S && y == ROOT)) {
continue;
}
if (exist(subtree[1], x)) {
bfs_edges[1].pb({id[{x, y}]});
} else {
//cout << "wtf: " << x << " " << y << endl;
bfs_edges[2].pb({id[{x, y}]});
}
}
//cout << "bfs 1: " << endl;
for (int el : bfs_edges[1]) {
int x = edge[el][0];
int y = edge[el][1];
//cout << x << " " << y << endl;
}
//cout << "bfs 2: " << endl;
for (int el : bfs_edges[2]) {
int x = edge[el][0];
int y = edge[el][1];
//cout << x << " " << y << endl;
}
s = find_ans(SUB_S, bfs_edges[1]); // log(n) - 1
t = find_ans(ROOT, bfs_edges[2]); // log(n) - 1
//answer(s, t);
if (s > t) {
swap(s, t);
}
answer(s, t);
//cout << "! " << s << " " << t << endl;
}
//signed main() {
//cin >> N;
//cin >> M;
//cin >> A;
//cin >> B;
//cin >> S;
//cin >> T;
//U.resize(M);
//V.resize(M);
//graph.assign(N, std::vector<std::pair<int, int>>());
//for (int i = 0; i < M; ++i) {
//cin >> U[i];
//cin >> V[i];
//graph[U[i]].push_back({V[i], i});
//graph[V[i]].push_back({U[i], i});
//}
//find_pair(N, U, V, A, B);
//}
