#include "citymapping.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
void find_roads(int n, int q, int A[], int B[], int W[]) {
vector <int> ii(n, 0);
vector <ll> c(n + 1, 0);
for (int i = 1; i <= n; i++) {
c[i] = get_distance(1, i);
}
iota(ii.begin(), ii.end(), 1);
stable_sort(ii.begin(), ii.end(), [&] (auto x, auto y) {
return c[x] < c[y];
});
if (q == 12000) {
vector <int> a[2] = {{1, ii[1]}, {1}};
int cur = 0;
for (int i = 2; i < n; i++) {
if (c[ii[i - 1]] + get_distance(ii[i - 1], ii[i]) != c[ii[i]]) {
cur ^= 1;
}
a[cur].push_back(ii[i]);
}
int cnt = 0;
for (int j = 0; j + 1 < (int)a[0].size(); j++) {
int idx = cnt; cnt++;
A[idx] = a[0][j]; B[idx] = a[0][j + 1];
W[idx] = c[a[0][j + 1]] - c[a[0][j]];
}
for (int j = 0; j + 1 < (int)a[1].size(); j++) {
int idx = cnt; cnt++;
A[idx] = a[1][j]; B[idx] = a[1][j + 1];
W[idx] = c[a[1][j + 1]] - c[a[1][j]];
}
return;
}
for (int i = 1; i <= n; i++) {
}
}
