#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define all(v) v.begin(), v.end()
#define pb push_back
#define ss second
#define ff first
#define vt vector
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair<int, int> pii;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
const int inf = 1e9;
const int mod = 1e9+7;
const int maxn = 1e4 + 1;
#include "stations.h"
#include <vector>
bool wt[maxn];
vt<int> g[maxn];
vt<pii> asgn;
int in[maxn], out[maxn], cnt;
void dfs(int i, int p){
in[i] = cnt++;
for(auto j : g[i]){
if(j == p)continue;
wt[j] = wt[i] ^ 1;
dfs(j, i);
}
out[i] = cnt++;
if(wt[i])asgn.pb({out[i], i});
else asgn.pb({in[i], i});
}
vector<int> label(int n, int k, vector<int> u, vector<int> v) {
vector<int> labels(n);
for(int i = 0; i < n - 1; i++){
g[u[i]].pb(v[i]), g[v[i]].pb(u[i]);
}
dfs(0, -1);
cnt = 0;
sort(all(asgn));
for(auto i : asgn){
labels[i.ss] = cnt++;
}
return labels;
}
int find_next_station(int s, int t, vector<int> c) {
sort(all(c));
if(s < c[0]){
for(auto i : c){
if(s <= t && t <= i)return i;
}
return c.back();
}
else {
reverse(all(c));
for(auto i : c){
if(s >= t && t >= i)return i;
}
return c[0];
}
}
//void solve() {
//}
//int main() {
//ios_base::sync_with_stdio(0);
//cin.tie(0);
//int times = 1;
////cin >> times;
//for(int i = 1; i <= times; i++) {
//solve();
//}
//return 0;
//}
