#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],siz[N];
void dfs0(ll x,ll fa){
siz[x]=1;
for(ll i=idx[x];i;i=ln[i].nxt){
if(ln[i].to==fa) continue;
dfs0(ln[i].to,x);
siz[x]+=siz[ln[i].to];
}
}
void dfs(ll x,ll fa,ll l,ll r){
if(dep[x]%2==0) dfn[x]=l;
else dfn[x]=r;
ll t=dfn[x];
// printf(":: %lld %lld %lld\n",x,l,r);
for(ll i=idx[x];i;i=ln[i].nxt){
if(ln[i].to==fa) continue;
dep[ln[i].to]=dep[x]+1;
if(dep[x]%2==0){
dfs(ln[i].to,x,t+1,t+siz[ln[i].to]);
t+=siz[ln[i].to];
}
else{
dfs(ln[i].to,x,t-siz[ln[i].to],t-1);
t-=siz[ln[i].to];
}
}
}
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;
for(ll i=0;i<u.size();i++) add_edge(u[i],v[i]);
dfs0(0,0);
dfs(0,0,1,n);
vector<int> lab;
for(ll i=0;i<n;i++) lab.push_back(dfn[i]);
// for(ll i=0;i<n;i++) printf("%lld ",siz[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];
}
// for(ll i=0;i<c.size();i++) printf("%lld ",c[i]);cout<<endl;
if(s<c[0]){
for(ll i=0;i<c.size()-1;i++){
if(s<t && t<c[i]) return c[i];
}
return c[c.size()-1];
}
else{//c[0]<s
for(ll i=c.size()-1;i>0;i--){
if(c[i]<t && t<s) return c[i];
}
return c[0];
}
//printf("%lld %lld\n",s,t);
}
