#include "citymapping.h"
#include <bits/stdc++.h>
using namespace std;
map<pair<int,int>,long long> m1;
int weight[1005];
vector<pair<int,int>> v3[1005];
vector< pair<long long, int> > v1;
vector<int> blocked;
bool block[1005];
vector<int> tour;
long long getdist(int x,int y) {
if (x==y) return 0;
if (x > y) swap(x,y);
if (!m1[make_pair(x,y)]){
return m1[make_pair(x,y)] = get_distance(x+1, y+1);
}
else return m1[make_pair(x, y)];
}
int dfs(int x, int p) {
int ans = 1;
tour.push_back(x);
for (int i = 0; i < v3[x].size(); i++){
if (!block[v3[x][i].first]){
ans += dfs(v3[x][i].first,x);
}
}
return weight[x] = ans;
}
void find_roads(int N, int Q, int A[], int B[], int W[]) {
int root = 0;
for (int i = 0; i < N; i++) {
if (i!=root) v1.push_back(make_pair(getdist(root, i), i));
}
sort(v1.begin(), v1.end());
for (int i = 0; i < v1.size(); i++) {
int currnode = v1[i].second;
long long dist = v1[i].first;
int currroot = root;
while (1) {
vector< pair<int, long long> > v2;
long long curd = 0;
tour.clear();
dfs(currroot, -1);
if (weight[currroot] == 1) {
A[i] = currnode + 1;
B[i] = currroot + 1;
W[i] = getdist(root, currnode) - getdist(root, currroot);
v3[currroot].push_back(make_pair(currnode, W[i]));
for (int j = 0; j < blocked.size(); j++) block[blocked[j]] = 0;
blocked.clear();
break;
}
int mnd = 1000000000, node = -1;
for (int j = 0; j < tour.size(); j++) {
if (max(weight[tour[j]], weight[currroot] - weight[tour[j]]) < mnd) {
mnd = max(weight[tour[j]], weight[currroot] - weight[tour[j]]);
node = tour[j];
}
}
long long d = getdist(currnode, node);
if (d + getdist(root, node) == getdist(root, currnode)) {
currroot = node;
} else {
block[node] = 1;
blocked.push_back(node);
}
}
}
}
