#include <bits/stdc++.h>
#include "citymapping.h"
using namespace std;
const int MAX_N = 1005;
int dist[MAX_N][MAX_N];
vector <pair <int, int>> graph[MAX_N];
vector <tuple <int, int, int>> tree;
bool visited[MAX_N];
void dfs(int u, int p) {
visited[u] = true;
if(p != -1) {
tree.emplace_back(u, p, dist[u][p]);
}
for(auto [w, v] : graph[u]) {
if(visited[v] == true) {
continue;
}
if(p == -1) {
dfs(v, u);
}
else {
if(dist[v][u] + dist[u][p] == dist[v][p]) {
dfs(v, u);
}
}
}
}
void find_roads(int N, int Q, int A[], int B[], int W[]) {
if(Q == 500000) {
for(int i = 1; i <= N; i++) {
for(int j = i + 1; j <= N; j++) {
dist[i][j] = dist[j][i] = get_distance(i, j);
graph[i].emplace_back(dist[i][j], j);
graph[j].emplace_back(dist[j][i], i);
}
}
for(int i = 1; i <= N; i++) {
sort(graph[i].begin(), graph[i].end());
}
dfs(1, -1);
for(int i = 0; i < N - 1; i++) {
A[i] = get <0> (tree[i]);
B[i] = get <1> (tree[i]);
W[i] = get <2> (tree[i]);
}
}
else if(Q == 12000) {
int furthest = 0, node = 1;
for(int i = 2; i <= N; i++) {
dist[1][i] = get_distance(1, i);
if(furthest < dist[1][i]) {
furthest = dist[1][i];
node = i;
}
}
vector <pair <int, int>> adj;
for(int i = 1; i <= N; i++) {
if(i == node) {
continue;
}
dist[node][i] = get_distance(node, i);
adj.emplace_back(dist[node][i], i);
}
sort(adj.begin(), adj.end());
int prv = node, prvDist = 0, M = 0;
for(auto [nowDist, now] : adj) {
A[M] = prv;
B[M] = now;
W[M] = nowDist - prvDist;
M++;
prvDist = nowDist;
prv = now;
}
}
else {
// do something
}
}
