#include "stations.h"
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> adj;
vector<int> lab;
int cnt;
void dfs (int u, int p = -1) {
for (int v : adj[u]) {
if (v ^ p) {
dfs(v, u);
}
}
lab[u] = cnt++;
}
void dfs2 (int u, int p, int lb) {
lab[u] = lb;
for (int v : adj[u]) {
if (v ^ p) {
dfs2(v, u, lb + 1);
}
}
}
bool subtask2 () {
for (int i = 0; i < (int)adj.size(); ++i) {
vector<int> y{(i - 1) / 2, 2 * i + 1, 2 * i + 2};
if (!i) {
y.erase(y.begin());
}
sort(adj[i].begin(), adj[i].end());
while (y.size() > adj[i].size()) {
y.pop_back();
}
if (y != adj[i]) {
return 0;
}
}
return 1;
}
vector<int> label(int n, int k, vector<int> u, vector<int> v) {
adj.assign(n, {});
lab.resize(n);
cnt = 0;
for (int i = 0; i < n - 1; ++i) {
adj[u[i]].push_back(v[i]);
adj[v[i]].push_back(u[i]);
}
if (subtask2()) {
iota(lab.begin(), lab.end(), 0);
return lab;
}
if (all_of(adj.begin(), adj.end(), [](auto &e) {return e.size() < 3;})) {
for (int i = 0; i < n; ++i) {
if (adj[i].size() == 1) {
dfs(i);
break;
}
}
return lab;
}
array<int, 2> p {0};
for (int i = 0; i < n; ++i) {
p = max(p, {(int)adj[i].size(), i});
}
int lb = 1e3;
lab[p[1]] = lb;
for (int v : adj[p[1]]) {
lb += 1e3;
dfs2(v, p[1], lb);
}
return lab;
}
int find_next_station(int s, int t, vector<int> c) {
if (c.size() == 1) {
return c[0];
}
int o = 1e3;
if (s >= o) {
if (s / o == t / o) {
return s - (t < s) + (t > s);
}
return s == o ? t / o * o : s % o ? s - 1 : o;
}
sort(c.begin(), c.end());
vector<int> y{(s - 1) / 2, 2 * s + 1, 2 * s + 2};
if (!s) {
y.erase(y.begin());
}
while (y.size() > c.size()) {
y.pop_back();
}
if (y != c) {
return s - (t < s) + (t > s);
}
int e = t;
while (e) {
int p = (e - 1) / 2;
if (p == s) {
return e;
}
e = p;
}
return (s - 1) / 2;
}
