#include "stations.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1000;
int tin[MAXN], tout[MAXN], depth[MAXN]; int t = 0;
vector<int> adj[MAXN];
vector<tuple<int, int, int>> subs;
void dfs(int v, int pai) {
// assert (t <= 10000);
// cerr << v << endl;
tin[v] = ((depth[v] & 1) == 0 ? t++ : t);
for (int viz : adj[v]) {
if (viz == pai) continue;
depth[viz] = depth[v] + 1;
dfs(viz, v);
}
tout[v] = (depth[v] & 1) ? t++ : t;
}
vector<int> label(int n, int k, vector<int> u, vector<int> v) {
// cerr << "here" << endl;
for (int i=0; i<n; i++) {
adj[i].clear();
t = 0;
}
for (int i=0; i<n-1; i++) {
int a = u[i], b = v[i];
adj[a].push_back(b);
adj[b].push_back(a);
}
dfs(0, -1);
vector<int> labels(n);
for (int i = 0; i < n; i++) {
labels[i] = (depth[i] & 1) ? tout[i] : tin[i];
}
return labels;
}
int find_next_station(int s, int t, vector<int> c) {
for (int viz : c) {
if (viz == t) return viz;
}
bool hasTin = s < c[0];
int pai = -1;
subs.clear();
if (hasTin) {
pai = (s == 0 ? -1 : c.back());
int l = s+1;
for (int viz : c) {
if (viz == pai) continue;
subs.emplace_back(viz, l, viz);
l = viz+1;
}
} else {
pai = c[0];
reverse(c.begin(), c.end());
int r = s-1;
for (int viz : c) {
if (viz == pai) continue;
subs.emplace_back(viz, viz, r);
r = viz-1;
}
}
for (auto [viz, l, r] : subs) {
if (l <= t and t <= r) return viz;
}
return pai;
}
