#include <iostream>
#include "stations.h"
#include <vector>
#include <algorithm>
#define ll long long
using namespace std;
const int N = 1002;
vector<int> g[N];
vector<int> labels;
int tin[N], tout[N];
int timer = 0;
int h[N];
void dfs(int v, int p) {
tin[v] = timer++;
for (int to : g[v]) {
if (p == to) continue;
h[to] = h[v] + 1;
dfs(to, v);
}
tout[v] = timer++;
}
vector<int> label(int n, int k, vector<int> u, vector<int> v) {
labels.resize(n, 0);
for (int i = 0; i < n; i++) {
g[i].clear();
}
timer = 0;
fill(h, h + n, 0);
for (int i = 0; i < n - 1; i++) {
g[u[i]].push_back(v[i]);
g[v[i]].push_back(u[i]);
}
dfs(0, -1);
for (int i = 0; i < n; i++) {
if (h[i] % 2 == 0) {
labels[i] = tin[i] / 2;
}
else {
labels[i] = tout[i] / 2;
}
//cout << i << " " << labels[i] << endl;
}
/*vector<int> c = {0, 1, 5};
cout << *(upper_bound(c.begin() + 1, c.end(), 5) - 1) << endl;
cout << "____________\n";*/
return labels;
}
int find_next_station(int s, int t, vector<int> c) {
if (c.size() == 1)
return c[0];
int n = c.size();
if (s == 0) {
return *lower_bound(c.begin(), c.end(), t);
}
if (s > c[0]) { // s@ tout a, c[0]-n hern a
int si = c[1], so = s;
if (t >= si && t <= so) {
return *(upper_bound(c.begin() + 1, c.end(), t) - 1);
}
else {
return c[0];
}
}
else { //s@ tin a, c[n-1]@ hern a
int si = s, so = c[n - 2];
if (t >= si && t <= so) {
return *lower_bound(c.begin(), c.end(), t);
}
else {
return c.back();
}
}
}
/*
1
12 2000
0 1
0 2
0 3
1 4
1 5
2 6
3 7
4 8
4 9
7 10
8 11
10
0 6 2
0 10 3
8 7 4
2 8 0
4 2 1
7 5 3
1 5 5
1 8 4
4 9 9
4 11 8
*/
