#include "stations.h"
#include<bits/stdc++.h>
using namespace std;
using ll = int;
using ull = unsigned long long;
using ld = long double;
#define pll pair <ll,ll>
#define fi first
#define se second
#define sz(a) (ll((a).size()))
#define BIT(mask,i) (((mask) >> (i))&1LL)
#define MASK(i) (1LL << (i))
#define MP make_pair
#define ms(a) memset(a,0,sizeof (a))
namespace {
vector <ll> g[200100];
ll sus[200100];
ll depth[200100];
ll timeDFS;
void dfs(ll u,ll p){
depth[u] = depth[p]+1;
if (depth[u]&1)sus[u]=timeDFS++;
for (auto v:g[u]){
if (v!=p)dfs(v,u);
}
if ((depth[u]&1)==0)sus[u]=timeDFS++;
}
}
std::vector<ll> label(ll n, ll k, std::vector<ll> u, std::vector<ll> v) {
std::vector<ll> labels(n);
for (ll i = 0;i < n;i ++)g[i].clear();
timeDFS = 0;
for (ll i = 0;i <= n - 2;i ++){
g[u[i]].push_back(v[i]);
g[v[i]].push_back(u[i]);
}
dfs(0,0);
for (ll i = 0;i < n;i ++){
labels[i] = sus[i];
}
return labels;
}
ll find_next_station(ll s, ll t, std::vector<ll> c) {
if (s>c[0]){
ll p = *c.begin();
c.erase(c.begin());
c.push_back(s+1);
for (ll i = 0;i + 1 < sz(c);i ++){
ll l=c[i],r=c[i+1]-1;
if (l <= t && t <= r){
return l;
}
}
return p;
}
else{
ll p = c.back();
if (s>0)c.pop_back();
c.insert(c.begin(),s-1);
for (ll i = 0;i + 1 < sz(c);i ++){
ll l=c[i]+1,r=c[i+1];
if (l <= t && t <= r){
return c[i+1];
}
}
return p;
}
}
