#include "stations.h"
#include <vector>
#include <bits/stdc++.h>
namespace label_call {
using std::vector;
using std::cout;
using std::max;
using std::endl;
vector<vector<int> > g;
int timer = 0;
vector<int> tin, tout, ans;
void dfs(int v, int par, int dep) {
tin[v] = timer;
timer += 1;
for(int child : g[v]) {
if(child == par) {
continue;
}
dfs(child, v, dep + 1);
}
tout[v] = timer;
timer += 1;
if(dep % 2 == 1) {
ans[v] = 2 * tout[v] + 1;
}
else {
ans[v] = 2 * tin[v];
}
}
} // namespace label_call
std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
using namespace label_call;
g.assign(n, vector<int>());
timer = 0;
tin.assign(n, -1);
tout.assign(n, -1);
ans.assign(n, -1);
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, 0);
// assert(*std::max_element(ans.begin(), ans.end()) <= 4100);
assert(*std::max_element(tout.begin(), tout.end()) <= 2000);
return ans;
}
namespace query_call {
using std::vector;
using std::cout;
using std::sort;
using std::endl;
}
int find_next_station(signed s, signed t, std::vector<signed> c) {
using namespace query_call;
if(c.size() == 1u) {
return c[0];
}
const int target_time = t/2;
int tin = -1, tout = -1;
if(s % 2 == 1) {
tout = s/2;
tin = c[1]/2 - 1;
assert(tin != tout and tout != target_time and tin != target_time);
if(target_time < tin or tout < target_time) {
return c[0];
}
const int child_cnt = c.size();
for(int i = child_cnt - 1; i >= 0; --i) {
const int child_tin = c[i]/2;
if(target_time >= child_tin) {
return c[i];
}
}
}
else {
sort(c.begin(), c.end(), std::greater<int>());
tin = s/2;
tout = c[1]/2 + 1;
if(target_time < tin or tout < target_time) {
return c[0];
}
const int child_cnt = c.size();
for(int i = child_cnt - 1; i >= 0; --i) {
const int child_tin = c[i]/2;
if(target_time <= child_tin) {
return c[i];
}
}
}
assert(false);
return -1;
}
/*
1
5 20
0 1
1 2
1 3
2 4
6
0 3 1
3 2 1
3 4 1
1 4 2
0 1 1
1
14 60
0 1
1 2
2 3
2 4
2 5
5 6
5 7
1 8
0 9
9 10
10 11
11 12
11 13
*/
