#include "citymapping.h"
#include<bits/stdc++.h>
#define ll long long
#define F first
#define S second
#define pb push_back
using namespace std;
bool wchek[1001];
bool vis[1001];
ll linkk[1001];
struct nd{
ll a,b,w;
};
vector<pair<ll,ll>>v;
vector<nd>res;
void dfs(ll node,ll p){
vis[node]=1;
vector<ll>no;
if(linkk[node]>=3)
return;
for(ll i=0;i<v.size();i++){
if(!vis[v[i].S] && wchek[v[i].S]){
ll d=get_distance(node,v[i].S);
if(d<v[i].F){
dfs(v[i].S,node);
linkk[node]++;
res.pb({node,v[i].S,d});
}else{
no.pb(v[i].S);
wchek[v[i].S]=0;
}
}
if(linkk[node]>=3)
break;
}
for(ll x:no){
wchek[x]=1;
}
return;
}
void find_roads(int n, int Q, int A[], int B[], int W[]) {
for(ll i=1;i<=1000;i++){
wchek[i]=true;
linkk[i]=0;
}
for(ll i=2;i<=n;i++){
ll d=get_distance(1, i);
v.pb({d,i});
}
sort(v.begin(),v.end());
ll c=0;
for(ll i=0;i<v.size();i++){
if(!vis[v[i].S]){
dfs(v[i].S,1);
A[c]=1;
B[c]=v[i].S;
W[c]=v[i].F;
c++;
linkk[1]++;
linkk[v[i].F]++;
}
if(c>=3)
break;
}
for(ll i=0;i<res.size();i++){
A[c]=res[i].a;
B[c]=res[i].b;
W[c]=res[i].w;
c++;
}
return;
}
