#include <bits/stdc++.h>
#include "stations.h"
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define F first
#define S second
#define endl '\n'
#define Mp make_pair
#define pb push_back
#define pf push_front
#define size(x) (ll)x.size()
#define all(x) x.begin(), x.end()
#define fuck(x) cout<<"("<<#x<<" : "<<x<<")\n"
const int N = 3e5 + 100, lg = 18;
const ll Mod = 1e9 + 7;
const ll inf = 1e18 + 10;
ll MOD(ll a, ll mod=Mod) {
a%=mod; (a<0)&&(a+=mod); return a;
}
ll poww(ll a, ll b, ll mod=Mod) {
ll res = 1;
while(b > 0) {
if(b%2 == 1) res = MOD(res * a, mod);
b /= 2;
a = MOD(a * a, mod);
}
return res;
}
int n, tin[N], h[N], tout[N], c1, c2;
vector<int> adj[N];
void dfs(int v, int p=-1) {
tin[v] = c1 ++;
for(int u : adj[v]) {
if(u == p) continue;
h[u] = 1 - h[v];
dfs(u,v);
}
tout[v] = c2 ++;
}
vector<int> label(int _n, int _k, vector<int> eu, vector<int> ev) {
n = _n;
c1 = c2 = 0;
for(int i=0; i<n-1; i++) {
adj[eu[i]].pb(ev[i]);
adj[ev[i]].pb(eu[i]);
}
dfs(0);
vector<int> res;
for(int i=0; i<n; i++) {
if(h[i] == 0) res.pb(tin[i]);
else res.pb(tout[i]);
}
for(int i=0; i<n; i++) adj[i].clear();
return res;
}
int find_next_station(int s, int t, vector<int> c) {
if(size(c) == 1) return c[0];
if(s <= c[0]) {
if(t < s) return c.back();
for(int i=0; i<size(c); i++) {
if(t <= c[i]) return c[i];
}
return c.back();
}
if(t > s) return c[0];
for(int i=size(c)-1; i>=0; i--) {
if(t >= c[i]) return c[i];
}
return c[0];
}
// int main() {
// label(5, 10, {0, 1, 1, 2}, {1, 2, 3, 4});
// // find_next_station()
// return 0;
// }
