#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <list>
#include <time.h>
#include <math.h>
#include <random>
#include <deque>
#include <queue>
#include <cassert>
#include <climits>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <bitset>
#include <sstream>
#include <chrono>
#include <cstring>
#include <optional>
//#define int long long
#define INP freopen("subrev.in","r",stdin)
#define OUTP freopen("subrev.out","w",stdout)
using ld = long double;
using LD = ld;
using namespace std;
const int maxn = 1200;
vector<vector<int> > v;
int lab[maxn];
int sz[maxn];
void dfs1(int u, int p = -1) {
sz[u] = 1;
for (auto a : v[u]) {
if (a == p) continue;
dfs1(a, u);
sz[u] += sz[a];
}
}
int cur = 0;
void dfs2(int u, bool isMin = true, int p = -1) {
if (isMin || (p != -1 && v[u].size() == 1)) {
lab[u] = cur++;
} else {
lab[u] = cur + sz[u] - 1;
}
if ((p != -1 && v[u].size() == 1)) return;
for (auto a : v[u]) {
if (a == p) continue;
dfs2(a, !isMin, u);
}
if (!isMin) {
cur++;
}
}
int find_next_station(int s, int t, vector<int> c) {
if (c.size() == 1) return c[0];
if (s < c[0]) {
int last = s + 1;
for (int i = 0; i < c.size() - 1; i++) {
if (c[i] == last ){
if (c[i] == t) return c[i];
else {
last++;
continue;
}
}
int r = c[i] - 1;
if (t >= last && t <= r) return c[i];
last = c[i] + 1;
}
return c.back();
} else {
int r = s - 1;
for (int i = c.size() - 1; i > 0; i--) {
if (c[i] == r) {
if (c[i] == t) return c[i];
else {
r--;
continue;
}
}
int l = c[i] + 1;
if (t >= l && t <= r) return c[i];
r = c[i] - 1;
}
return c[0];
}
}
vector<int> label(int n, int k, vector<int> a, vector<int> b) {
v.clear();
v.resize(a.size() + 10);
cur = 0;
for (int i = 0; i < a.size() + 10; i++) {
sz[i] = 0;
lab[i] = 0;
}
for (int i = 0; i < a.size(); i++) {
v[a[i]].push_back(b[i]);
v[b[i]].push_back(a[i]);
}
dfs1(0);
dfs2(0);
vector<int> res;
for (int i = 0; i < a.size() + 1; i++) res.push_back(lab[i]);
return res;
}
/*
void solve() {
vector<int> res = label(12, 12, {0, 0, 0, 2, 2, 2, 8, 8, 8, 3, 4}, {1, 2, 3, 6, 7, 8, 9, 10, 11, 4, 5});
cout << find_next_station(10, 11, {11, 12});
}
int main() {
ios_base::sync_with_stdio(0);
solve();
}
*/
