#include "stations.h"
#include "bits/stdc++.h"
using namespace std;
#define all(x) begin(x),end(x)
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { string sep; for (const T &x : v) os << sep << x, sep = " "; return os; }
#define debug(a) cerr << "(" << #a << ": " << a << ")\n";
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pi;
const int mxN = 1e5+1, oo = 1e9;
int cnt = 0;
void dfs(vvi& adj, vi& label, int at=0, int from=-1, bool odd = false) {
if(!odd) label[at] = cnt++;
for(int to: adj[at]) if(to!=from) {
dfs(adj,label,to,at,!odd);
}
if(odd) label[at] = cnt++;
}
vi label(int n, int k, vector<int> u, vector<int> v) {
vi labels(n);
cnt=0;
vvi adj(n);
for(int i=0;i<n-1;++i) {
adj[u[i]].push_back(v[i]);
adj[v[i]].push_back(u[i]);
}
dfs(adj,labels);
return labels;
}
int find_next_station(int s, int t, std::vector<int> c) {
for(int to: c) if(to==t) return to;
if(s<c[0]) {
// s has in label
int parentout = c.back();
c.insert(c.begin(),s);
int n = c.size();
for(int i=1;i<n;++i) {
if(c[i-1]< t and t<c[i]) {
return c[i];
}
}
return parentout;
} else {
// s has out label
int parentin = c[0];
c.push_back(s);
int n = c.size();
for(int i=2;i<n;++i) {
if(c[i-1]<t and t <c[i]) {
return c[i-1];
}
}
return parentin;
}
}
