#include "citymapping.h"
//#include <iostream>
#include <functional>
#include <algorithm>
#include <numeric>
#include <vector>
using namespace std;
#define ll long long
typedef struct {
int to;
ll d;
} edge_t;
void find_roads(int N, int Q, int A[], int B[], int W[]) {
if (Q <= 12000) {
int start;
{
ll maxd = 0;
for (int i = 2; i <= N; i++) {
ll d = get_distance(1, i);
if (d > maxd) {
maxd = d;
start = i;
}
}
}
vector<ll> dists(N);
dists[start-1] = 0;
vector<int> ids(N);
iota(ids.begin(), ids.end(), 0);
for (int i = 1; i <= N; i++) {
if (i == start) continue;
dists[i-1] = get_distance(start,i);
}
sort(ids.begin(), ids.end(), [&](int a, int b) {
return dists[a] < dists[b];
});
for (int i = 0; i < N-1; i++) {
A[i] = ids[i]+1;
B[i] = ids[i+1]+1;
W[i] = dists[ids[i+1]] - dists[ids[i]];
}
} else {
vector<ll> dists(N*N, -1);
auto ds = [&](int i_, int j_){
i_--;
j_--;
int i = min(i_, j_);
int j = max(i_, j_);
if (dists[i+j*N] == -1) {
dists[i+j*N] = get_distance(i+1, j+1);
}
return dists[i+j*N];
};
int out_idx = 0;
auto output = [&](int x, int y, int dist) {
A[out_idx] = x;
B[out_idx] = y;
W[out_idx++] = dist;
};
// for (int i = 1; i <= N; i++) {
// for (int j = i+1; j <= N; j++) {
// // if (get_distance(i,j) == 1) {
// // A[k] = i;
// // B[k] = j;
// // W[k++] = 1;
// // }
// dists[i+j*N] = dists[j+i*N] = get_distance(i,j);
// }
// }
std::function<void(vector<edge_t>&, int)> rec = [&](vector<edge_t> &edges, int x) -> void {
if (edges.size() == 0) return;
vector<edge_t> sub;
vector<edge_t> rest;
int y = edges[0].to;
output(x, y, edges[0].d);
for (edge_t edge : edges) {
if (edge.to == x || edge.to == y) continue;
ll dist = ds(y, edge.to);
if (dist < edge.d) {
sub.push_back({.to = edge.to, .d = ds(y, edge.to)});
} else {
rest.push_back(edge);
}
}
sort(sub.begin(), sub.end(), [](edge_t a, edge_t b) {
return a.d < b.d;
});
rec(sub, y);
rec(rest, x);
};
vector<edge_t> edges;
for (int i = 2; i <= N; i++) {
ll dist = ds(1, i);
edges.push_back({.to = i, .d = dist});
}
sort(edges.begin(), edges.end(), [](edge_t a, edge_t b) {
return a.d < b.d;
});
rec(edges, 1);
}
}
