#include "stations.h"
#include<bits/stdc++.h>
using namespace std;
using ll = int;
#define pll pair <ll,ll>
#define fi first
#define se second
#define MP make_pair
#define sz(a) (ll((a).size()))
#define BIT(mask,i) (((mask) >> (i))&1)
#define MASK(i) (1LL<<(i))
const ll MAXN = 1010;
vector <ll> g[MAXN];
vector <ll> labels;
ll timeDFS;
void dfs(ll u,ll p,bool dep){
if (dep==0)labels[u]=timeDFS++;
for (auto v:g[u]){
if (v==p)continue;
dfs(v,u,1-dep);
}
if (dep==1)labels[u]=timeDFS++;
}
std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
timeDFS = 0;
for (ll i = 0;i < n;i++)g[i].clear();
for (ll i = 0;i < sz(u);i ++){
g[u[i]].push_back(v[i]);
g[v[i]].push_back(u[i]);
}
labels.resize(n);
dfs(0,0,0);
return labels;
}
int find_next_station(int s, int t, std::vector<int> c) {
bool dep = 0;
for (auto x:c)if (x < s)dep = 1;
if (dep){
c.push_back(s);
for (ll j = 1;j + 1 < sz(c);j ++){
if (c[j] <= t && t < c[j+1])return c[j];
}
return c[0];
}
else{
c.insert(c.begin(),s);
for (ll i = 1;i + 1 < sz(c);i ++){
if (c[i-1] <= t && t <= c[i])return c[i];
}
return c.back();
}
return c[0];
}
