#include "stations.h"
#include <vector>
#include<bits/stdc++.h>
using namespace std;
int a,b,c,d,e,i,j,ii,jj,zx,xc,tim,lf[1009],rg[1009],dep[1009],pi;
vector <int> v[1009];
pair <int, int> p[1009];
void dfs(int q, int w){
if(w!=-1) dep[q]=dep[w]+1;
tim++;
lf[q]=tim;
for(vector <int>::iterator it=v[q].begin(); it!=v[q].end(); it++){
if((*it)==w) continue;
dfs((*it),q);
}
tim++;
rg[q]=tim;
if(dep[q]%2==0){
pi++;
p[pi].first=lf[q];
p[pi].second=q;
}else{
pi++;
p[pi].first=rg[q];
p[pi].second=q;
}
}
vector<int> label(int n, int kk, vector<int> U, vector<int> V) {
vector<int> labels(n);
pi=0;tim=0;
for(i=0; i<=n; i++){
v[i].clear();
dep[i]=0;
lf[i]=rg[i]=0;
}
for(i=0; i<n-1; i++){
v[U[i]].push_back(V[i]);
v[V[i]].push_back(U[i]);
}
//cout<<pi<<" ra "<<endl;
dfs(0,-1);
sort(p+1,p+pi+1);
//cout<<pi<<" kd "<<endl;
for(i=1; i<=pi; i++){
//cout<<p[i].first<<" "<<p[i].second<<endl;
labels[p[i].second]=i-1;
}
return labels;
}
int find_next_station(int s, int t, std::vector<int> C) {
for(i=0; i<C.size(); i++){
if(C[i]==t){
return t;
}
}
e=0;
for(i=0; i<C.size(); i++){
if(C[i]>s){
e=1;
break;
}
}
if(e==0){
sort(C.begin(),C.end());
for(i=1; i<C.size(); i++){
if(t>=C[i-1]&&t<C[i]){
return C[i-1];
}
}
if(t>=C[C.size()-1]&&t<s){
return C[C.size()-1];
}
return C[0];
}else{
sort(C.begin(),C.end());
if(s==0){
for(i=0; i<C.size(); i++){
if(t<=C[i]){
return C[i];
}
}
}else{
if(t<s){
return C[C.size()-1];
}
for(i=0; i<C.size(); i++){
if(i+1>=C.size()) break;
if(t<=C[i]){
return C[i];
}
}
return C[C.size()-1];
}
}
}
