#include "stations.h"
#include<bits/stdc++.h>
using namespace std;
vector<int>adj[1000];
int tin[1000],tout[1000],color[1000];
int timer = -1;
void dfs(int v,int u){
tin[v] = ++timer;
for(int x:adj[v]){
if(x==u)continue;
color[x] = color[v]^1;
dfs(x,v);
}
tout[v] = ++timer;
}
vector<int> label(int n, int k, vector<int> u, vector<int> v) {
for(int i=0;i<n;i++)adj[i].clear();
vector<int>lab(n);
for(int i=0;i+1<n;i++){
adj[v[i]].push_back(u[i]);
adj[u[i]].push_back(v[i]);
}
timer = -1;
dfs(0,-1);
for(int i=0;i<n;i++){
if(color[i])lab[i] = tin[i];
else lab[i] = tout[i];
}
vector<int>crd;
for(int x:lab)crd.push_back(x);
sort(crd.begin(),crd.end());
crd.resize(unique(crd.begin(),crd.end()) - crd.begin());
for(int &x:lab)x = lower_bound(crd.begin(),crd.end(),x) - crd.begin();
return lab;
}
int find_next_station(int s, int t, vector<int> c) {
int n = c.size();
if(c.back() > s){
//s label is tin
int last = s;
for(int i=0;i+1<n;i++){
int l = last+1;
int r = c[i];
if(l <= t && t <= r)return c[i];
last = c[i];
}
return c.back();
}else{
//s label is tout
int last = s;
for(int i=n-1;i>0;i--){
int l = c[i];
int r = last-1;
if(l <= t && t <= r)return c[i];
last = c[i];
}
return c[0];
}
}
