#include "stations.h"
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> adj;
vector<int> lab;
int cnt;
void dfs (int u, int p = -1) {
for (int v : adj[u]) {
if (v ^ p) {
dfs(v, u);
}
}
lab[u] = cnt++;
}
vector<int> label(int n, int k, vector<int> u, vector<int> v) {
adj.assign(n, {});
lab.resize(n);
cnt = 0;
for (int i = 0; i < n - 1; ++i) {
adj[u[i]].push_back(v[i]);
adj[v[i]].push_back(u[i]);
}
if (all_of(adj.begin(), adj.end(), [](auto &e) {return e.size() < 3;})) {
for (int i = 0; i < n; ++i) {
if (adj[i].size() == 1) {
dfs(i);
break;
}
}
return lab;
}
iota(lab.begin(), lab.end(), 0);
return lab;
}
int find_next_station(int s, int t, vector<int> c) {
if (c[0] != (s - 1) / 2) {
return s - (t < s) + (t > s);
}
int e = t;
while (e) {
int p = (e - 1) / 2;
if (p == s) {
return e;
}
e = p;
}
return (s - 1) / 2;
}
