#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;
}
void create_tree() {
// найти ребро на пути S -> T
vector <int> w(m);
for (int i = 0; i < m; i++) {
w[i] = 0;
}
w[0] = 1;
ll cur_cost = ask(w);
int root = -1;
int sub = -1;
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 = edge[r][1];
queue <int> q;
vector <int> dist(MAXN, -1);
dist[root] = 0;
q.push(root);
ROOT = root;
SUB_S = sub;
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 pr[MAXN];
int d[MAXN];
void calc(int v, int par, int len) {
pr[v] = par;
d[v] = len;
for (pii to : tree[v]) {
if (to.fr != par) {
calc(to.fr, v, len + 1);
}
}
}
void dfs(int v, int par, int len, vector <pii> &possible) {
for (pii to : tree[v]) {
if (to.fr != par) {
if (len + 1 == diametr) {
possible.pb({to.fr, to.sc});
}
dfs(to.fr, v, len + 1, possible);
}
}
}
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});
}
create_tree(); // log(n) queries
int l = -1, r = szof(bfs_edges) - 1;
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 = 0; i <= mid; i++) {
w[bfs_edges[i]] = 1;
}
ll cur_cost = ask(w);
if (cur_cost != max_path) {
l = mid;
} else {
r = mid;
}
}
calc(ROOT, -1, 0);
int last_edge = bfs_edges[r];
int x = edge[last_edge][0], y = edge[last_edge][1];
int my_s = (d[x] > d[y] ? x : y);
vector <pii> possible;
dfs(my_s, -1, 0, possible);
// possible.fr vertex
// possible.sc edge real id
l = 0, r = szof(possible) - 1;
while (l != r) {
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 = l; i <= mid; i++) {
w[possible[i].sc] = 1;
}
ll cur_cost = ask(w);
if (cur_cost == min_path) {
l = mid + 1;
} else {
r = mid;
}
}
answer(my_s, possible[l].fr);
}
