/* by Natsu Kinmoe */
#include <bits/stdc++.h>
using namespace std;
#define SZ(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define loop(i, n) for(int i = 0; i < (n); i++)
#define cont(i, n) for(int i = 1; i <= (n); i++)
#define circ(i, a, b) for(int i = (a); i <= (b); i++)
#define range(i, a, b, c) for(int i = (a); ((c) > 0 ? i <= (b) : i >= (b)); i += (c))
#define foreach(it, v) for(__typeof((v).begin()) it = (v).begin(); it != (v).end(); it++)
#define y0 y0O0OO00OO0OO0OO0OOO00OO0OO0O0O000OO0
#define y1 y1II11II11III11I1III11II111IIII1II1I1
#define pub push_back
#define pob pop_back
#define mak make_pair
typedef long long ll;
typedef long double lf;
const int Inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3fll;
/* Source code starts here */
#include "stations.h"
vector<int> label(int n, int k, vector<int> u, vector<int> v) {
vector<vector<int> > nei(n);
loop(i, n - 1) nei[u[i]].pub(v[i]), nei[v[i]].pub(u[i]);
vector<int> res(n);
int tmc = 0;
function<void(int, int, int)> dfs = [&](int now, int lst, int lvl) {
if(lvl == 0) res[now] = ++tmc;
loop(i, SZ(nei[now])) {
int to = nei[now][i];
if(to == lst) continue;
dfs(to, now, lvl ^ 1);
}
if(lvl == 1) res[now] = ++tmc;
};
dfs(0, -1, 0);
return res;
}
int find_next_station(int s, int t, vector<int> c) {
vector<int> cs = c;
int fa;
sort(all(cs));
if(cs[0] > s) fa = cs.back(), cs.pob(), cs.insert(cs.begin(), s);
else fa = cs[0], cs.erase(cs.begin()), cs.pub(s);
loop(i, SZ(cs)) if(cs[i] == t) return t;
loop(i, SZ(cs) - 1) {
int l = cs[i], r = cs[i + 1];
if(t >= l && t <= r) {
if(cs[0] == s) return r;
else return l;
}
}
return fa;
}
