// Ignut
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e5 + 123;
const int C = 1000;
vector<int> tree[N];
vector<int> euler;
int root;
void dfs(int v, int par) {
euler.push_back(v);
for (int to : tree[v]) {
if (to != par) {
dfs(to, v);
if (v == root)
euler.push_back(v);
}
}
}
vector<int> label(int n, int k, vector<int> u, vector<int> v) {
euler.clear();
for (int i = 0; i < n; i ++) {
tree[i].clear();
}
for (int i = 0; i < n - 1; i ++) {
tree[u[i]].push_back(v[i]);
tree[v[i]].push_back(u[i]);
}
root = 0;
for (int i = 0; i < n; i ++)
if (tree[i].size() > 2)
root = i;
dfs(root, -1);
vector<int> lbl(n);
lbl[root] = 0;
int val = 0;
for (int v : euler) {
if (v == root) {
val = ((val / C) + 1) * C;
val ++;
continue;
}
lbl[v] = val;
val ++;
}
return lbl;
}
const int INF = 1e9 + 123;
int find_next_station(int s, int t, vector<int> c) {
if (c.size() == 1)
return c[0];
for (int v : c)
if (v == t)
return t;
bool isRoot = true;
for (int v : c) {
if (v % C != 1)
isRoot = false;
}
if (isRoot) {
for (int v : c) {
if (v / C == t / C)
return v;
}
while (true);
return c[0];
}
//
if (c.size() != 2)
while (true);
int mn = min(c[0], c[1]);
int mx = max(c[0], c[1]);
if (mx / C == t / C) {
// we are in the correct chain
if (mx % C <= t % C)
return mx;
return mn;
}
// we are in the incorrect chain
return mn;
}
