#include "bits/stdc++.h"
#include "stations.h"
using namespace std;
vector<int> leaf, p;
vector<vector<int> > adj;
void dfs(int node, int par){
p[node] = par;
if(node != par && adj[node].size() == 1){
leaf.push_back(node);
}
for(auto itr: adj[node]){
if(itr == par) continue;
dfs(itr, node);
}
}
vector<int> label(int n, int k, vector<int> u, vector<int> v) {
p.assign(n, 0);
adj.resize(n);
for(int i = 0; i < n; i++){
adj[i].clear();
}
leaf.clear();
for(int i = 0; i < n-1; i++){
adj[u[i]].push_back(v[i]);
adj[v[i]].push_back(u[i]);
}
dfs(0, 0);
int now = 0;
vector<int> labels(n), cnt(n);
labels[0] = n-1;
for(auto itr: leaf){
int cur = itr;
while(p[cur] != cur){
labels[cur] = now++;
cnt[p[cur]]++;
if(cnt[p[cur]] == adj[p[cur]].size()-1){
cur = p[cur];
}
else{
break;
}
}
}
return labels;
}
int find_next_station(int s, int t, vector<int> c) {
int nxt = -1;
for(auto itr: c){
if(itr >= t){
nxt = itr;
break;
}
}
if(nxt != -1) return nxt;
else return c[c.size()-1];
}
