#include <bits/stdc++.h>
#include "stations.h"
using namespace std;
/*⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣤⠀⠀⠀⠀⠀⠀⠀⡄⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣤⣿⠛⣿⠀⠀⠀⠀⣤⣿⢻⡇⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣤⣿⡛⠀⣤⣿⣿⣤⣤⣿⣿⣤⢸⡇⠀
⠀⠀⠀⠀⠀⠀⠀⠀⣴⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡇⠀
⠀⠀⠀⠀⠀⠀⠀⣶⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡗⠀
⢠⣼⣿⣿⣿⣿⣤⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷
⢸⣿⣿⡟⠛⠛⢿⣿⣿⣿⣿⣿⣿⣿⣤⣤⣤⣿⣿⣿⣿⣤⣤⣼⣿⣿
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠘⠛⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡟⠋
*/
#define fi first
#define se second
#define pb push_back
#define ins insert
#define sz(a) (int)(a.size())
#define all(x) (x).begin(),(x).end()
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
void print(){cout<<'\n';}
template<class h,class...t>
void print(const h&v,const t&...u){cout<<v<<' ',print(u...);}
#define ONLINE_JUDGE
#ifndef ONLINE_JUDGE
#include "debug.h"
#else
#define debug(...)
#endif
//const int mod = 1e9+7;
//const int mod = 998244353;
const int MAXN=2e5+5;
const ll inf=1e9,INF=1e18;
void dfs(int v,int p,int d,int &timer,vector<vi> &g,vi &in,vi &out,vi &val) {
in[v] = timer++;
for(int i : g[v]) {
if(i == p) continue;
dfs(i,v,d+1,timer,g,in,out,val);
} out[v] = timer++;
if(d % 2) val[v] = in[v];
else val[v] = out[v];
}
vector<int> label(int n, int k, vector<int> u, vector<int> v) {
vector<vi> g(n); vi in(n),out(n),val(n),cmp(2*n+1);
for(int i=0;i<n-1;i++) g[u[i]].pb(v[i]),g[v[i]].pb(u[i]);
int timer = 0;
dfs(0,-1,0,timer,g,in,out,val);
vi tmp = val; sort(all(tmp));
for(int i=0;i<n;i++) cmp[tmp[i]] = i;
for(int i=0;i<n;i++) val[i] = cmp[val[i]];
return val;
}
int find_next_station(int s, int t, vector<int> c) {
bool odd = 1; sort(all(c));
for(int i : c) {
odd &= (i > s);
}
if(odd) {
for(int i : c) {
if(t >= s and t <= i) return i;
} return c.back();
} else {
if(t > s) return c.front();
for(int i=1;i<c.size()-1;i++) {
if(c[i] <= t and t < c[i+1]) return c[i];
}
if(c.back() <= t and t < s) return c.back();
return c.front();
}
}
