#ifndef EVAL
#include "stub.cpp"
#endif
#include "stations.h"
#include <bits/stdc++.h>
#define fr first
#define sc second
#define pii pair<int, int>
#define pb push_back
#define szof(s) (int)s.size()
#define all(s) s.begin(), s.end()
using namespace std;
const int MAXN = 1005;
vector <int> g[MAXN];
void save(int v, int par, vector <int> &order) {
order.pb(v);
for (int to : g[v]) {
if (par != to) {
save(to, v, order);
}
}
}
void clean() {
for (int i = 0; i < MAXN; i++) {
g[i].clear();
}
}
vector<int> label(int n, int k, vector<int> u, vector<int> v) {
clean();
for (int i = 0; i <= n - 2; i++) {
int x = u[i];
int y = v[i];
g[x].pb(y);
g[y].pb(x);
}
int root = -1;
for (int i = 0; i < n; i++) {
if (szof(g[i]) == 1) {
root = i;
break;
}
}
vector <int> order;
save(root, -1, order);
vector <int> labels(n);
for (int i = 0; i < n; i++) {
int cur = order[i];
labels[cur] = i;
}
return labels;
}
int find_next_station(int s, int t, vector<int> c) {
int left = min(s, t);
int right = max(s, t);
for (int el : c) {
if (left <= el && el <= right) {
return el;
}
}
assert(false);
return -1;
}
