#include "citymapping.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr ll inf = 1e15;
void find_roads(int N, int Q, int A[], int B[], int W[]) {
int r = -1;
ll mx = 0;
for (int i = 1; i < N; i++) {
assert(Q--);
ll s = get_distance(1, i + 1);
if (s > mx) {
mx = s;
r = i;
}
}
vector<ll> dis(N);
for (int i = 0; i < N; i++) {
assert(Q--);
dis[i] = i == r ? 0 : get_distance(r + 1, i + 1);
}
vector<int> p(N);
iota(p.begin(), p.end(), 0);
sort(p.begin(), p.end(), [&](int i, int j) {
return dis[i] < dis[j];
});
vector<vector<int>> d(N);
d[0].push_back(r);
for (int i = 1; i < N; i++) {
int v = p[i];
vector<bool> f(N);
int lo = 0, hi = N - 1;
while (lo < hi) {
int mi = (lo + hi + 1) / 2;
bool ok = 0;
for (int x : d[mi]) {
assert(Q--);
if (dis[v] - dis[x] == get_distance(x + 1, v + 1)) {
f[x] = 1;
ok = 1;
}
}
if (ok) {
lo = mi;
} else {
hi = mi - 1;
}
}
int u = -1;
for (int x : d[lo]) {
if (f[x]) {
u = x;
}
}
if (u == -1) {
for (int x : d[lo]) {
assert(Q--);
if (dis[v] - dis[x] == get_distance(x + 1, v + 1)) {
u = x;
break;
}
}
}
A[i - 1] = u + 1;
B[i - 1] = v + 1;
W[i - 1] = dis[v] - dis[u];
d[lo + 1].push_back(v);
}
}
