#include <bits/stdc++.h>
#include "citymapping.h"
#define pb push_back
using namespace std;
void find_roads(int N, int Q, int A[], int B[], int W[]) {
// get N, Q
// pick a lucky number: 1
// find the difference of 1 and all other nodes
vector<pair<long long, int>> dis1; // {distance, node}
for (int i = 2; i <= N; i ++) {
dis1.pb({get_distance(1, i), i});
}
sort(dis1.begin(), dis1.end());
// get longest distance node
int longest_dis_node = dis1[N-2].second;
vector<pair<long long, int>> dis2;
for (int i = 1; i <= N; i ++) {
if (i == longest_dis_node) {continue;}
dis2.pb({get_distance(longest_dis_node, i), i});
}
sort(dis2.begin(), dis2.end());
int cur = 0;
for (int i = 0; i < N-1; i ++) {
A[i] = longest_dis_node;
B[i] = dis2[i].second;
W[i] = dis2[i].first-cur;
cur = dis2[i].first;
}
}
