#include "stations.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e3+10;
struct edge{
ll to,nxt;
}ln[N*2];
ll idx[N],topln;
void add_edge(ll u,ll v){
ln[++topln]=(edge){v,idx[u]},idx[u]=topln;
ln[++topln]=(edge){u,idx[v]},idx[v]=topln;
}
ll dep[N],dfn[N],L,R;
void dfs(ll x,ll fa){
if(dep[x]%2==0) dfn[x]=L,L++;
else dfn[x]=R,R--;
// printf("%lld %lld\n",x,dfn[x]);
for(ll i=idx[x];i;i=ln[i].nxt){
if(ln[i].to==fa) continue;
dep[ln[i].to]=dep[x]+1;
dfs(ln[i].to,x);
}
}
vector<int> label(int n, int k, vector<int> u, vector<int> v) {
memset(dep,0,sizeof(dep));
memset(dfn,0,sizeof(dfn));
memset(idx,0,sizeof(idx));
topln=0;
L=1,R=n;
for(ll i=0;i<u.size();i++) add_edge(u[i],v[i]);
dfs(0,0);
vector<int> lab;
for(ll i=0;i<n;i++) lab.push_back(dfn[i]);
//for(ll i=0;i<n;i++) printf("%lld ",dfn[i]);cout<<endl;
return lab;
}
int find_next_station(int s, int t, vector<int> c) {
for(ll i=0;i<c.size();i++){
if(t==c[i]) return c[i];
}
if(s<c[0]){
if(t<s || t>c[c.size()-1]) return c[c.size()-1];
for(ll i=0;i<c.size()-1;i++){
if(t<c[i]) return c[i];
}
}
else{//c[0]<s
if(s<t || t<c[0]) return c[0];
for(ll i=1;i<c.size();i++){
if(c[i]<t) return c[i];
}
}
//printf("%lld %lld\n",s,t);
}
