// kodumu runlayabilir misin canim cms
// sihirli kelimeyi de soyleyeyim lutfen :((
#include "citymapping.h"
// void piri_reis(int N, int Q, int A[], int B[], int W[]){
// int X = gezinti(5, 4);
// X = gezinti(2, 4);
// X = gezinti(1, 3);
// X = gezinti(1, 2);
// A[0] = 3, A[1] = 4, A[2] = 4, A[3] = 5;
// B[0] = 4, B[1] = 1, B[2] = 2, B[3] = 3;
// W[0] = 7, W[1] = 8, W[2] = 1, W[3] = 3;
// return;
// }
#include "bits/stdc++.h"
using i64 = long long;
#ifdef DEBUG
#include "../debug.h"
#else
#define debug(...) void(23)
#endif
int N;
std::vector<int> A, B, W;
std::map<std::pair<int ,int>, i64> save;
i64 ask(int a, int b) {
if (a > b) {
std::swap(a, b);
} else if (a == b) {
return 0;
}
if (save.contains({a, b})) {
return save[{a, b}];
}
return save[{a, b}] = get_distance(a, b);
}
std::random_device rd;
std::mt19937 rng(rd());
int get(int l, int r) {
return l + rng() % (r - l + 1);
}
std::pair<int, std::vector<i64>> bfs(int s, std::vector<int> v) {
int n = int(v.size());
std::vector<i64> dis(n);
for (int i = 0; i < n; ++i) {
dis[i] = ask(s, v[i]);
}
int mx = 0;
for (int i = 0; i < n; ++i) {
if (dis[i] > dis[mx]) {
mx = i;
}
}
return {mx, dis};
}
void kodumu_runla_lutfen(int come_from_god, std::vector<int> v) {
int n = int(v.size());
if (n == 1) {
return;
}
debug(v);
int leaf1, leaf2;
std::vector<i64> dis1, dis2;
if (come_from_god != -1) {
leaf1 = come_from_god;
auto[l2, d1] = bfs(v[leaf1], v);
leaf2 = l2;
dis1 = d1;
auto[___, d2] = bfs(v[leaf2], v);
dis2 = d2;
} else {
auto[y, d] = bfs(v[0], v);
leaf1 = y;
auto[l2, d1] = bfs(v[leaf1], v);
leaf2 = l2;
dis1 = d1;
auto[___, d2] = bfs(v[leaf2], v);
dis2 = d2;
}
debug(leaf1, v[leaf1], dis1);
debug(leaf2, v[leaf2], dis2);
std::vector<int> ondia(n);
for (int i = 0; i < n; ++i) {
// debug(dis1[i] + dis2[i], dis2[leaf2]);
if (dis1[i] + dis2[i] == dis1[leaf2]) {
ondia[i] = true;
}
}
std::vector<int> dia;
for (int i = 0; i < n; ++i) {
if (ondia[i]) {
dia.emplace_back(i);
}
}
std::sort(dia.begin(), dia.end(), [&](auto lhs, auto rhs) {
return dis1[lhs] < dis1[rhs];
});
int m = int(dia.size());
// #ifdef DEBUG
// debug("diameter:");
// for (int i = 0; i < m; ++i) {
// debug(v[dia[i]]);
// }
// #endif
for (int i = 0; i < m - 1; ++i) {
int j = dia[i], k = dia[i + 1];
A.emplace_back(v[j]);
B.emplace_back(v[k]);
W.emplace_back(dis1[k] - dis1[j]);
}
std::vector<std::vector<int>> g(m);
for (int i = 0; i < n; ++i) {
if (ondia[i]) {
continue;
}
int lo = 1, hi = m - 2;
while (lo < hi) {
int mid = (lo + hi + 1) >> 1;
if (dis1[dia[mid]] + ask(v[dia[mid]], v[i]) == dis1[i]) {
lo = mid;
} else {
hi = mid - 1;
}
}
// debug(v[i], lo);
g[lo].emplace_back(i);
}
for (int i = 0; i < m; ++i) {
if (g[i].empty()) {
continue;
}
int sizg = int(g[i].size());
int mn = 0, mx = 0;
for (int j = 0; j < sizg; ++j) {
if (dis1[g[i][j]] < dis1[g[i][mn]]) {
mn = j;
}
if (dis1[g[i][j]] > dis1[g[i][mx]]) {
mx = j;
}
}
// debug(v[dia[i]], v[g[i][mn]]);
A.emplace_back(v[dia[i]]);
B.emplace_back(v[g[i][mn]]);
W.emplace_back(dis1[g[i][mn]] - dis1[dia[i]]);
std::vector<int> yolla(sizg);
for (int j = 0; j < sizg; ++j) {
yolla[j] = v[g[i][j]];
}
kodumu_runla_lutfen(mx, yolla);
}
}
void solve_sub(int come_from_god, std::vector<int> v) {
int n = int(v.size());
if (n == 1) {
return;
} else if (n == 2) {
A.emplace_back(v[0]);
B.emplace_back(v[1]);
W.emplace_back(ask(v[0], v[1]));
return;
} else if (n <= 10) {
kodumu_runla_lutfen(come_from_god, v);
return;
}
std::shuffle(v.begin(), v.end(), rng);
// debug(v);
// int leaf1, leaf2;
// std::vector<i64> dis1, dis2;
// if (come_from_god != -1) {
// leaf1 = come_from_god;
// auto[l2, d2] = bfs(v[leaf1], v);
// leaf2 = l2;
// dis2 = d2;
// auto[___, d1] = bfs(v[leaf2], v);
// dis1 = d1;
// } else {
// auto[y, d] = bfs(v[0], v);
// leaf1 = y;
// auto[l2, d2] = bfs(v[leaf1], v);
// leaf2 = l2;
// dis2 = d2;
// auto[___, d1] = bfs(v[leaf2], v);
// dis1 = d1;
// }
int leaf1 = 0;
int leaf2 = 1;
leaf2 += (leaf2 == leaf1);
auto[__, dis1] = bfs(v[leaf1], v);
auto[___, dis2] = bfs(v[leaf2], v);
debug(leaf1, v[leaf1], dis1);
debug(leaf2, v[leaf2], dis2);
std::vector<int> ondia(n);
for (int i = 0; i < n; ++i) {
debug(dis1[i] + dis2[i], dis1[leaf2]);
if (dis1[i] + dis2[i] == dis1[leaf2]) {
ondia[i] = true;
}
}
std::vector<int> dia;
for (int i = 0; i < n; ++i) {
if (ondia[i]) {
dia.emplace_back(i);
}
}
std::sort(dia.begin(), dia.end(), [&](auto lhs, auto rhs) {
return dis1[lhs] < dis1[rhs];
});
int m = int(dia.size());
#ifdef DEBUG
debug("diameter:");
for (int i = 0; i < m; ++i) {
debug(v[dia[i]]);
}
#endif
for (int i = 0; i < m - 1; ++i) {
int j = dia[i], k = dia[i + 1];
A.emplace_back(v[j]);
B.emplace_back(v[k]);
W.emplace_back(dis1[k] - dis1[j]);
}
std::vector<std::vector<int>> g(m);
for (int i = 0; i < n; ++i) {
if (ondia[i]) {
continue;
}
int lo = 0, hi = m - 1;
while (lo < hi) {
int mid = (lo + hi + 1) >> 1;
if (dis1[dia[mid]] + ask(v[dia[mid]], v[i]) == dis1[i]) {
lo = mid;
} else {
hi = mid - 1;
}
}
debug(v[i], lo);
g[lo].emplace_back(i);
}
for (int i = 1; i < m - 1; ++i) {
if (g[i].empty()) {
continue;
}
int sizg = int(g[i].size());
int mn = 0, mx = 0;
for (int j = 0; j < sizg; ++j) {
if (dis1[g[i][j]] < dis1[g[i][mn]]) {
mn = j;
}
if (dis1[g[i][j]] > dis1[g[i][mx]]) {
mx = j;
}
}
debug(v[dia[i]], v[g[i][mn]]);
A.emplace_back(v[dia[i]]);
B.emplace_back(v[g[i][mn]]);
W.emplace_back(dis1[g[i][mn]] - dis1[dia[i]]);
std::vector<int> yolla(sizg);
for (int j = 0; j < sizg; ++j) {
yolla[j] = v[g[i][j]];
}
solve_sub(mx, yolla);
}
for (int i : {0, m - 1}) {
if (g[i].empty()) {
continue;
}
int sizg = int(g[i].size());
std::vector<int> yolla(sizg);
for (int j = 0; j < sizg; ++j) {
yolla[j] = v[g[i][j]];
}
yolla.emplace_back(v[dia[i]]);
solve_sub(-1, yolla);
}
}
void solve() {
std::vector<int> all;
all.resize(N);
std::iota(all.begin(), all.end(), 1);
solve_sub(-1, all);
// debug(A);
// debug(B);
// debug(W);
}
void find_roads(int N, int Q, int A[], int B[], int W[]) {
::N = N;
solve();
for (int i = 0; i < N - 1; ++i) {
A[i] = ::A[i];
B[i] = ::B[i];
W[i] = ::W[i];
}
return;
}
