#include "stations.h"
#include <vector>
#include<bits/stdc++.h>
using namespace std;
vector<vector<int>> di;
map<int,int> mp;
int si;
vector<int> label(int n, int k, vector<int> u, vector<int> v) {
vector<int> labels(n);
si=n;
int i,j,ku;
int lab=k;
for (int i = 0; i < n; i++) {
labels[i] = i%k;
mp[i%k]=i;
}
vector<vector<int>> nig(n,vector<int>(n,INT_MAX));
for(i=0;i<n-1;i++){
nig[u[i]][v[i]]=1;
nig[v[i]][u[i]]=1;
}
for(i=0;i<n;i++){
nig[i][i]=0;
}
for(i=0;i<n;i++){
for(j=0;j<n;j++){
if(nig[i][j]==INT_MAX)continue;
for(ku=0;ku<n;ku++){
if(nig[i][ku]==INT_MAX)continue;
nig[j][ku]=min(nig[j][ku],nig[j][i]+nig[i][ku]);
nig[ku][j]=nig[j][ku];
}
}
}
di=move(nig);
return labels;
}
int find_next_station(int s, int t, vector<int> c) {
int i,j;
int mn=INT_MAX,jum;
for(i=0;i<c.size();i++){
int hah=di[mp[c[i]]][t];
if(hah<mn){
mn=hah;
jum=c[i];
}
}
return jum;
}
