#include <bits/stdc++.h>
#include "citymapping.h"
using namespace std;
const int nax = 1002;
struct Dsu {
int par[nax];
int sz[nax];
Dsu() {
for(int i = 0; i < nax; i++) {
par[i] = i;
sz[i] = 1;
}
}
int find(int v) {
if (v == par[v]) {
return v;
}
return par[v] = find(par[v]);
}
bool unite(int a, int b) {
a = find(a), b = find(b);
if (a == b) return false;
if (sz[b] > sz[a]) swap(a, b);
par[b] = a;
sz[a] += sz[b];
return true;
}
};
int dist[nax][nax];
void find_roads(int N, int Q, int A[], int B[], int W[]) {
vector<array<int, 3>> d;
for(int i = 1; i <= N; i++) {
for(int j = i+1; j <= N; j++) {
dist[i][j] = get_distance(i, j);
d.push_back({dist[i][j], i, j});
}
}
sort(d.begin(), d.end());
Dsu dsu;
int idx = 0;
for(auto& i : d) {
if (dsu.unite(i[1], i[2])) {
A[idx] = i[1];
B[idx] = i[2];
W[idx] = i[0];
idx++;
}
}
return;
}
