#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>());
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);
// cout << "Time \n--------------------\n";
// for(int i = 0; i < n; ++i) {
// cout << i << " : " << tin[i] << ' ' << tout[i] << endl;
// }
// cout << "\n-----------------\n";
// cout << "Labels\n-------------------\n";
// for(int i = 0; i < n; ++i) {
// cout << i << " : " << ans[i] << endl;
// }
// cout << "---------------\n";
return ans;
}
namespace query_call {
using std::vector;
using std::cout;
using std::sort;
using std::endl;
}
int find_next_station(int s, int t, std::vector<int> c) {
using namespace query_call;
// cout << "hi " << s << ' ' << t << " : ";
// cout << "[";
// for(int x : c)
// cout << x << ' ';
// cout << "] ";
if(c.size() == 1u) {
// printf("ans : %d\n", c[0]);
return c[0];
}
const int target_time = t/2;
// cout << target_time << endl;
int tin = -1, tout = -1;
if(s % 2) {
sort(c.begin(), c.end());
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) {
// printf("ans : %d\n", c[0]);
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) {
// printf("ans : %d\n", c[i]);
return c[i];
}
}
// assert(false);
// cout << "odd end\n";
}
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) {
// printf("ans : %d\n", c[0]);
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) {
// printf("ans : %d\n", c[i]);
return c[i];
}
}
// cout << "even end\n";
}
assert(false);
// cout << "wtf\n";
return -1;
}
/*
1
5 20
0 1
1 2
1 3
2 4
6
0 3 1
0 4 1
0 2 1
0 1 1
3 0 1
1 4 2
*/
