#include "stations.h"
#include <bits/stdc++.h>
#define rep(i,n)for(int i=0;i<int(n);i++)
using namespace std;
typedef long long ll;
static vector<vector<int>>E;
static vector<int>labels;
void dfs(int v,int p,int l){
labels[v]=l;
for(int u:E[v]){
if(u==p)continue;
dfs(u,v,l+1);
}
}
std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v){
E=vector<vector<int>>(n);
labels=vector<int>(n);
vector<int>deg(n);
rep(i,n-1){
E[u[i]].push_back(v[i]);
E[v[i]].push_back(u[i]);
deg[u[i]]++;
deg[v[i]]++;
}
int s=max_element(deg.begin(),deg.end())-deg.begin();
if(deg[s]==2){
s=min_element(deg.begin(),deg.end())-deg.begin();
}
int x=1;
for(int u:E[s]){
dfs(u,s,x);
x+=1000;
}
return labels;
}
int find_next_station(int s, int t, std::vector<int> c) {
if(s==0){
int nx=((t-1)/1000)*1000+1;
return nx;
}
if((s-1)/1000==(t-1)/1000){
return s<t?s+1:s-1;
}
if(s%1000==1)return 0;
return s-1;
}
