#include "stations.h"
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
vector<int> adj[1010], ans;
bool visited[1010];
int cur=0;
void dfs(int s, int dep){
if (!(dep&1)) ans[s] = cur++;
visited[s] = 1;
for (auto &v:adj[s]) if (!visited[v]){
dfs(v, dep+1);
}
if (dep&1) ans[s] = cur++;
}
vector<int> label(int n, int k, vector<int> u, vector<int> v) {
for (int i=0;i<n;i++){
adj[i].clear(); visited[i] = 0;
}
ans.clear();
ans.resize(n);
cur = 0;
for (int i=0;i<n-1;i++){
adj[u[i]].push_back(v[i]);
adj[v[i]].push_back(u[i]);
}
dfs(0, 0);
return ans;
}
int find_next_station(int s, int t, vector<int> c) {
int l, r;
if (!s) l = 0, r = c.back();
else if (c[0]<s){
r = s;
if ((int)c.size()<2) l = s;
else l = c[1];
}
else{
l = s;
if ((int)c.size()<2) r = s;
else r = c[c.size()-2];
}
if (l<=t && t<=r){
auto iter = upper_bound(c.begin(), c.end(), t);
return *(--iter);
}
else{
if (c[0]<s) return c[0];
else return c.back();
}
}
