#include "stations.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> label(int n, int k, vector<int> u, vector<int> v) {
vector<vector<int>> adj(n+1);
for(int i=0;i<n-1;i++){
adj[u[i]].push_back(v[i]);
adj[v[i]].push_back(u[i]);
}
vector<int> lbl(n);
int ans=0;
for (int i=0; i<n; i++){
if (adj[i].size()>2){ans=i;}
}
queue <pair<int,pair<int,int>>> q;
int visited[n]={0};
visited[ans]=1;
lbl[ans]=0;
for (int i=0; i<adj[ans].size(); i++){
q.push({adj[ans][i],{i+1,1}});
}
while (q.size()){
auto x = q.front();
q.pop();
int node=x.first;
int depth=x.second.second;
int color=x.second.first;
if (visited[node]==0){
visited[node]=1;
lbl[node]=color*1000+depth;
for (int i=0; i<adj[node].size(); i++){
q.push({adj[node][i],{color,depth+1}});
}
}
}
return lbl;
}
int find_next_station(int s, int t, vector <int> cp){
if (s==0){
for (int i=0; i<cp.size(); i++){
if (cp[i]/1000==t/1000){return cp[i];}
}
return cp[0];
}
else if(s/1000!=t/1000){
return cp[0];
}
else{
if(t<s){
return cp[0];
}
else{
return cp[1];
}
}
return cp[0];
}
