#include "stations.h"
#include <bits/stdc++.h>
#define sz(x) (int)(x.size())
using namespace std;
const int N = 1000;
vector<int> edges[N];
vector<int> tin(N), tout(N);
int t1, t2;
void dfs(int x, int p) {
int y;
tin[x] = t1;
++t1;
while (!edges[x].empty()) {
y = edges[x].back();
edges[x].pop_back();
if (y != p) {
dfs(y, x);
}
}
tout[x] = t2;
++t2;
}
vector<int> label(int n, int k, vector<int> u, vector<int> v) {
vector<int> codes(n);
t1 = 0, t2 = 0;
for (int i = 0; i < n-1; ++i) {
edges[u[i]].push_back(v[i]);
edges[v[i]].push_back(u[i]);
}
dfs(0, -1);
for (int i = 0; i < n; ++i) {
// cout << sz(edges[i]) << "\n";
codes[i] = tin[i]*1000 + tout[i];
}
return codes;
}
int find_next_station(int s, int e, vector<int> c) {
int sin = s/1000, sout = s % 1000;
int ein = e/1000, eout = e % 1000;
if (ein < sin || eout > sout) {
for (int x : c) {
if ((x/1000) <= sin) {
return x;
}
}
}
for (int x : c) {
if ((x/1000) > sin && (x/1000) <= ein && (x%1000) >= eout) {
return x;
}
}
return -1;
}
// void solve() {
// vector<int> labels = label(3, 1000000000, {2, 1}, {0, 0});
// for (auto x : labels) {
// cout << x << " ";
// cout << "\n";
// }
// cout << "\n";
// cout << find_next_station(labels[1], labels[0], {labels[0]}) << "\n";
// cout << find_next_station(labels[1], labels[2], {labels[0]}) << "\n";
// cout << find_next_station(labels[2], labels[1], {labels[0]}) << "\n";
// cout << find_next_station(labels[0], labels[2], {labels[2], labels[1]}) << "\n";
// cout << find_next_station(labels[2], labels[0], {labels[0]}) << "\n";
// cout << find_next_station(labels[0], labels[1], {labels[2], labels[1]}) << "\n";
// // cout << "\n";
// // cout << find_next_station(1003, 4001, {2000, 3002, 4}) << "\n";
// }
// int main() {
// ios_base::sync_with_stdio(0);
// cin.tie(0);
// // int t;
// // cin >> t;
// // while (t--)
// solve();
// return 0;
// }
// static int max_label = 0;
// static int r, n, k, q;
// static std::vector<int> u, v, labels, answers;
// static std::map<int, int> reverse_labels;
// static std::vector<std::vector<int>> adjlist;
// static int s, t, w;
// static std::vector<int> c;
// int main() {
// assert(scanf("%d", &r) == 1);
// for (int tc = 0; tc < r; tc++) {
// assert(scanf("%d%d", &n, &k) == 2);
// u.resize(n - 1);
// v.resize(n - 1);
// adjlist.clear();
// adjlist.resize(n);
// for (int i = 0; i < n - 1; i++) {
// assert(scanf("%d%d", &u[i], &v[i]) == 2);
// adjlist[u[i]].push_back(v[i]);
// adjlist[v[i]].push_back(u[i]);
// }
// labels = label(n, k, u, v);
// if ((int)labels.size() != n) {
// printf("Number of labels not equal to %d\n", n);
// exit(0);
// }
// reverse_labels.clear();
// for (int i = 0; i < n; i++) {
// if (labels[i] < 0 || labels[i] > k) {
// printf("Label not in range 0 to %d\n", k);
// exit(0);
// }
// if (reverse_labels.find(labels[i]) != reverse_labels.end()) {
// printf("Labels not unique\n");
// exit(0);
// }
// reverse_labels[labels[i]] = i;
// if (labels[i] > max_label) {
// max_label = labels[i];
// }
// }
// assert(scanf("%d", &q) == 1);
// for (int i = 0; i < q; i++) {
// assert(scanf("%d%d%d", &s, &t, &w) == 3);
// c.clear();
// for (int v : adjlist[s]) {
// c.push_back(labels[v]);
// }
// std::sort(c.begin(), c.end());
// int answer = find_next_station(labels[s], labels[t], c);
// if (!std::binary_search(c.begin(), c.end(), answer)) {
// printf("Label %d returned by find_next_station not found in c\n", answer);
// exit(0);
// }
// answers.push_back(reverse_labels[answer]);
// }
// }
// printf("%d\n", max_label);
// for (int index : answers) {
// printf("%d\n", index);
// }
// exit(0);
// }
