#include "citymapping.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define inf 5e18
const ll N = 1001;
vector<pair<ll,ll>> g[N];
ll sz[N], hvy[N], no[N];
ll dist[N][N];
void dfs(ll v){
sz[v] = 1;
hvy[v] = 0;
ll mx = 0;
for(auto [ch, w] : g[v]){
if(no[ch]) continue;
dfs(ch);
sz[v] += sz[ch];
if(mx < sz[ch]){
mx = sz[ch];
hvy[v] = ch;
}
}
}
ll leaf(ll v){
if(hvy[v] == 0) return v;
return leaf(hvy[v]);
}
ll dis(ll a, ll b){
if(a == b) return 0;
if(a > b) swap(a, b);
if(dist[a][b]) return dist[a][b];
return dist[a][b] = get_distance(a, b);
}
ll find(ll v, ll d){
if(dis(1, v) == d) return v;
return find(hvy[v], d);
}
bool cmp(ll a, ll b){
return dis(1, a) < dis(1, b);
}
void find_roads(int n, int Q, int A[], int B[], int W[]){
ll a[n];
iota(a, a+n, 1);
sort(a, a+n, cmp);
for(ll i=1; i<n; i++){
fill(no, no+N, 0);
ll x = a[i], r = 1;
while(1){
dfs(r);
ll l = leaf(r);
if(l == r) break;
r = find(r, (dis(1, l) + dis(1, x) - dis(x, l))/2);
no[hvy[r]] = 1;
}
A[i-1] = r;
B[i-1] = x;
W[i-1] = dis(1, x) - dis(1, r);
g[r].push_back({x, W[i-1]});
}
}
