#include "stations.h"
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
#define pb push_back
#define pii pair<int, int>
#define pll pair<ll, ll>
#define st first
#define nd second
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#define debug false
const int MAXN = 1000 + 17;
vector<int> graf[MAXN];
int lev[MAXN];
int cnt = 0;
int nr[MAXN];
void DFS1 (int v, int o) {
for (auto x : graf[v]) {
if (x != o) {
lev[x] = lev[v] + 1;
DFS1(x, v);
}
}
}
void DFS2 (int v, int o) {
if (lev[v] % 2 == 0) {
nr[v] = cnt;
cnt ++;
}
for (auto x : graf[v]) {
if (x != o) {
DFS2(x, v);
}
}
if (lev[v] % 2 == 1) {
nr[v] = cnt;
cnt ++;
}
}
vector<int> label(int n, int k, vector<int> u, vector<int> v) {
vector<int> labels(n);
for (int i = 0; i < n; i ++) {
graf[i].clear();
}
for(int i=0;i<u.size();i++){
graf[u[i]].push_back(v[i]);
graf[v[i]].push_back(u[i]);
}
cnt = 0;
DFS1(0, 0);
DFS2(0, 0);
for (int i = 0; i < n; i ++) {
labels[i] = nr[i];
}
return labels;
}
int find_next_station(int v, int u, vector<int> c) {
sort(c.begin(), c.end());
int r = int(c.size());
if (v > c.back()) {
for (int i = 1; i < r - 1; i ++) {
if (c[i] <= u && u < c[i + 1]) {
return c[i];
}
}
if (c[r - 1] <= u && u < v) {
return c[r - 1];
}
return c[0];
}
for (int i = 1; i < r - 1; i ++) {
if (c[i - 1] < u && u <= c[i]) {
return c[i];
}
}
if (v < u && u <= c[0]) {
return c[0];
}
return c[r - 1];
}
