#include "stations.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1003;
vector<int> rel[maxn];
int depth[maxn];
int in[maxn];
int out[maxn];
int t = 0;
void dfs (int u, int p) {
depth[u] = depth[p] + 1;
in[u] = t++;
for (auto v : rel[u]) {
if (v == p) continue;
dfs(v, u);
}
out[u] = t++;
}
vector<int> label(int n, int k, vector<int> u, vector<int> v) {
for (int i = 0; i < n; i++) {
rel[i].clear();
}
t = 0;
vector<int> labels(n);
for (int i = 0; i < n - 1; i++) {
rel[u[i]].push_back(v[i]);
rel[v[i]].push_back(u[i]);
}
dfs(0, 0);
for (int i = 0; i < n; i++) {
if (depth[i] % 2 == 0) {
labels[i] = (in[i] << 1);
} else {
labels[i] = (out[i] << 1) + 1;
}
//printf("%d = %d, since in[i] = %d, out[i] = %d, depth[i] = %d\n", i, labels[i], in[i], out[i], depth[i]);
}
return labels;
}
int find_depth_par (int s, int t, vector<int> c) {
int tval = t >> 1;
int my_in = s >> 1;
set<int> outs;
for (auto v : c) outs.insert(v);
int parent = *outs.rbegin();
int my_out = (*++outs.rbegin()) >> 1;
if (my_in <= tval && tval <= my_out) {
set<int> contains;
for (auto v : c) {
if (v == parent) continue;
int his_out = v >> 1;
if (tval <= his_out) contains.insert(v);
}
return *contains.begin();
}
return parent;
}
int find_depth_impar (int s, int t, vector<int> c) {
int tval = t >> 1;
int my_out = s >> 1;
set<int> outs;
for (auto v : c) outs.insert(v);
int parent = *outs.begin();
int my_in = (*++outs.begin());
if (my_in <= tval && tval <= my_out) {
set<int> ins;
for (auto v : c) {
if (v == parent) continue;
int his_in = v >> 1;
if (his_in <= tval) ins.insert(v);
}
return *ins.rbegin();
}
return parent;
}
int find_next_station(int s, int t, vector<int> c) {
if (c.size() == 1) return c[0];
if ((s & 1) == 0) return find_depth_par(s, t, c);
else return find_depth_impar(s, t, c);
}
