#include <bits/stdc++.h>
using namespace std;
void dfs(int node, int par, int dist, vector<int> &lab, vector<vector<int>> &adj)
{
for (int child : adj[node])
{
if (child == par)
continue;
lab[child] = dist * 1000 + lab[node];
dfs(child, node, dist + 1, lab, adj);
}
}
vector<int> label(int n, int k, vector<int> u, vector<int> v)
{
vector<vector<int>> adj(n);
for (int i = 0; i < u.size(); i++)
{
adj[u[i]].push_back(v[i]);
adj[v[i]].push_back(u[i]);
}
int root = -1;
for (int i = 0; i < n; i++)
{
if (adj[i].size() > 2)
{
root = i;
break;
}
}
if (root == -1)
{
root = 0;
}
vector<int> lab(n, -1);
lab[root] = 0;
int cnt = 1;
for (int u : adj[root])
{
lab[u] = cnt++;
}
for (int u : adj[root])
{
dfs(u, root, 1, lab, adj);
}
return lab;
}
int find_next_station(int s, int t, vector<int> c)
{
for (int x : c)
{
if (x <= t && (x == 0 || x % 1000 == t % 1000))
return x;
}
return c[0];
}
