#include <bits/stdc++.h>
#include "stations.h"
using namespace std;
#define ll long long
// #define int ll
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
#define REP1(i, n) FOR(i, 1, n+1)
#define RREP(i, n) for (int i = (n)-1; i >= 0; i--)
#define pii pair<int, int>
// #define f first
//#define s second
#define pb push_back
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) (int)((x).size())
static const ll maxn = 1e3+5;
static vector<int> g[maxn];
static vector<int> lab(maxn);
void dfs(int u, int pre, int poo){
lab[u] = -1;
for (auto v:g[u]){
if (v == pre) continue;
dfs(v, u, poo);
lab[u] = lab[v]+1;
}
if (lab[u] == -1) lab[u] = poo+1;
}
std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
std::vector<int> labels(n);
REP(i, n) g[i].clear();
REP(i, n-1){
g[u[i]].pb(v[i]);
g[v[i]].pb(u[i]);
}
int spec = 0;
REP(i, n){
if (SZ(g[i]) > 2) spec = i;
}
REP(i, SZ(g[spec])){
int toad = i*1000;
dfs(g[spec][i], spec, toad);
}
REP(i, n) labels[i] = lab[i];
labels[spec] = 0;
return labels;
}
int find_next_station(int s, int t, std::vector<int> c) {
if (SZ(c) == 1) return c[0];
if (s == 0){
for (auto v:c) if (v/1000 == t/1000) return v;
}
int bg = c[0], sm = c.back();
if (bg < sm) swap(bg, sm);
if (sm == 0){
swap(bg, sm);
}
if (t == 0){
return bg;
}
if (s/1000 != t/1000){
return bg;
}
if (s > t){
return sm;
}
else return bg;
}
