#include "stations.h"
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#define dbg(x) (cout << (x))
#else
#define dbg(x)
#endif
typedef long long ll;
using vi =vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
#define pb push_back
#define FOR(i, a, b) for (int i = a; i < b; i++)
#define trace(x) for (auto &el : x) {dbg(el); dbg(" ");}
int n, k;
vi U, V, labels;
vvi adj;
int cur_label = 0;
int timer = 0;
vi tin, tout;
void dfs(int u, int p, bool depth) {
tin[u] = timer++;
for (auto &v : adj[u]) {
if (v == p) continue;
dfs(v, u, !depth);
}
tout[u] = timer++;
labels[u] = depth ? tin[u] : tout[u];
}
vi label(int N, int K, vi x, vi y) {
n = N; k = K;
U = x; V = y;
cur_label = 0;
tin.assign(n, 0); tout.assign(n, 0);
timer = 0;
adj.assign(n, vi());
vi deg(n); for (int i = 0; i < n - 1; i++) {
deg[U[i]]++, deg[V[i]]++;
adj[U[i]].push_back(V[i]);
adj[V[i]].pb(U[i]);
}
labels.assign(n, 0);
dfs(0, 0, true);
trace(labels); dbg("\n");
return labels;
}
int find_next_station(int s, int t, vi c) {
int tin, tout; bool is_tin;
if (s != 0) {
is_tin = true; for (auto &el : c) is_tin = is_tin && s <= el;
tin = is_tin ? s : c[min((int) c.size() - 1, 1)] - 1;
tout = is_tin ? c[c.size() == 1 ? c[0] : c.size() - 2] : s;
} else {
is_tin = true;
tin = 0;
tout = 1000;
}
if (s != 0 && !(tin <= t && t <= tout)) return is_tin ? c.back() : c.front();
for (int i = 0; i < c.size(); i++) {
int child_in = -1, child_out = -1;
if (is_tin && i < c.size() - 1) {
if (i == 0) child_in = (tin+1);
else child_in = (c[i-1]);
child_out = (c[i]);
} else if (!is_tin && i > 0) {
child_in = (c[i]);
if (i == c.size() - 1) child_out = (tout);
else child_out = (c[i+1]);
}
if (child_in != -1 && child_out != -1) {
if (child_in <= t && t <= child_out) return c[i];
}
}
return c[0]; // shouldn't occur
}
