#include "citymapping.h"
#include <bits/stdc++.h>
using namespace std;
const int Nmax = 1005;
typedef long long ll;
int nr = 0, root, n, sz[Nmax], up[Nmax], where[Nmax], last[Nmax], crt_chain;
ll dist[Nmax][Nmax];
vector<int> v[Nmax];
mt19937 mt(time(0));
int get_rand(int x, int y)
{
return uniform_int_distribution<int> (x, y) (mt);
}
ll get_dist(int x, int y)
{
if(x == y) return 0;
if(dist[x][y]) return dist[x][y];
return dist[x][y] = dist[y][x] = get_distance(x, y);
}
void add_edge(int V[], int U[], int cost[], int x, int y)
{
if(dist[root][x] > dist[root][y]) swap(x, y);
V[nr] = x;
U[nr] = y;
cost[nr] = dist[root][y] - dist[root][x];
v[x].push_back(y);
up[y] = x;
++nr;
}
int get_lca(int x, int y)
{
ll D = (get_dist(root, x) + get_dist(root, y) - get_dist(x, y)) / 2;
while(dist[root][x] != D)
x = up[x];
return x;
}
void dfs0(int node)
{
sz[node] = 1;
for(auto it : v[node])
{
dfs0(it);
sz[node] += sz[it];
}
sort(v[node].begin(), v[node].end(), [](int x, int y) {return sz[x] > sz[y];});
}
void hp(int node)
{
where[node] = crt_chain;
if(v[node].empty())
{
last[crt_chain] = node;
return;
}
hp(v[node][0]);
for(int i=1; i<v[node].size(); ++i)
{
++crt_chain;
hp(v[node][i]);
}
}
void process(int node, int V[], int U[], int cost[])
{
dfs0(root);
crt_chain = 1;
hp(root);
int x = last[1];
while(1)
{
int lca = get_lca(x, node);
if(lca == x)
{
add_edge(V, U, cost, x, node);
return;
}
if(lca == root)
{
if(v[root].size() == 1)
{
add_edge(V, U, cost, root, node);
return;
}
if(v[root].size() == 2)
{
if(where[x] == 1)
{
x = last[where[v[root][1]]];
continue;
}
else
{
add_edge(V, U, cost, root, node);
return;
}
}
if(v[root].size() == 3)
{
if(where[x] == 1)
{
x = last[where[v[root][1]]];
continue;
}
else
{
x = last[where[v[root][2]]];
continue;
}
}
}
if(v[lca].size() == 1)
{
add_edge(V, U, cost, lca, node);
return;
}
else if(v[lca].size() == 2)
x = last[where[v[lca][1]]];
}
}
void find_roads(int N, int Q, int A[], int B[], int W[])
{
n = N;
root = get_rand(1, n);
int i;
for(i=1; i<=n; ++i) get_dist(root, i);
vector<int> ord(n);
iota(ord.begin(), ord.end(), 1);
sort(ord.begin(), ord.end(), [](int x, int y) {return dist[root][x] < dist[root][y]; });
for(auto it : ord)
if(it != root)
process(it, A, B, W);
}
