#include "stations.h"
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 1e3 + 5;
vector<vector<int>> g(MAX_N);
int Time = -1, in[MAX_N], out[MAX_N];
void dfs(int node, int p) {
in[node] = ++Time;
for (auto to : g[node]) {
if (to != p) {
dfs(to, node);
}
}
out[node] = Time;
}
vector<int> label(int n, int k, vector<int> u, vector<int> v) {
Time = -1;
g.clear(); g.resize(MAX_N);
vector<int> labels(n);
for (int i = 0; i < n - 1; i++) {
g[u[i]].emplace_back(v[i]);
g[v[i]].emplace_back(u[i]);
}
dfs(0, -1);
for (int i = 0; i < n; i++) {
labels[i] = in[i] * 1000 + out[i];
}
return labels;
}
pair<int, int> extract(int mask) {
int out_time = mask % 1000;
mask /= 1000;
return make_pair(mask, out_time);
}
bool is_sub(int s, int t) {
pair<int, int> a= extract(s);
pair<int, int> b= extract(t);
return (a.first <= b.first && a.second >= b.second);
}
int find_next_station(int s, int t, vector<int> c) {
if (is_sub(s, t)) {
for (auto mask : c) {
if (is_sub(s, mask) && is_sub(mask, t)) {
return mask;
}
}
assert(false);
}
if (is_sub(t, s)) {
for (auto mask : c) {
if (is_sub(t, mask) && is_sub(mask, s)) {
return mask;
}
}
assert(false);
}
for (auto mask : c) {
if (is_sub(mask, s)) {
return mask;
}
}
assert(false);
}
