#include "stations.h"
#include <vector>
using namespace std;
vector<vector<int>> adj;
int N;
pair<short int, vector<int>> dfs(const int x, const int goal, vector<int>& curPath, vector<bool>& vis) {
if (x == goal) return {1, curPath};
for (int i : adj[x]) {
if (vis[i]) continue;
curPath.push_back(i);
vis[i] = true;
if (auto ans = dfs(i, goal, curPath, vis); ans.first != -1) return ans;
curPath.pop_back();
vis[i] = false;
}
return {-1, curPath};
}
std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
N = n;
vector<int> labels(n);
adj.resize(n);
for (int i = 0; i < n; i++) {
labels[i] = i;
}
for (int i = 0; i < n -1; i++) {
adj[u[i]].push_back(v[i]);
adj[v[i]].push_back(u[i]);
}
return labels;
}
int find_next_station(int s, int t, std::vector<int> c) {
vector<int> path;
vector<bool> vis(N, false);
return dfs(s, t, path, vis).second[0];
}
