#include "stations.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 5;
int t, tin[N], tout[N];
vector<int> tree[N], labels;
void dfs1(int v, int p, int x){
labels[v] = x;
for(auto e : tree[v]){
if(e != p) dfs1(e, v, x + 1);
}
}
void dfsgood(int v, int p){
tin[v] = ++t;
for(auto e : tree[v]){
if(e != p) dfsgood(e, v);
}
tout[v] = t;
}
vector<int> label(int n, int k, vector<int> u, vector<int> v){
labels.assign(n, -1);
for(int i = 0; i < n; i++) tree[i].clear(), tin[i] = tout[i] = 0;
for(int i = 0; i < n - 1; i++){
tree[u[i]].push_back(v[i]);
tree[v[i]].push_back(u[i]);
}
if(k == 1000){ // subtask 1, 2
int mx = 0;
for(int i = 0; i < n; i++) mx = max(mx, (int)tree[i].size());
if(mx <= 2){ // subtask 1
for(int i = 0; i < n; i++){
if(tree[i].size() == 1){
dfs1(i, 0, 0);
break;
}
}
}
else{
for(int i = 0; i < n; i++) labels[i] = i;
}
}
else{ // subtask 3, 4, 5
t = -1;
dfsgood(1, 0);
for(int i = 0; i < n; i++) labels[i] = tout[i] * 1000 + tin[i];
}
return labels;
}
bool ispar(int ain, int aout, int bin, int bout){
if(bin >= ain && bout <= aout) return true;
else return false;
}
int find_next_station(int s, int t, vector<int> c){
if(c.size() == 0) return c[0];
else{
if(c.size() == 2 && c[0] == s - 1 && c[1] == s + 1){ // subtask 1
if(t < s) return c[0];
else return c[1];
}
else if(s < 1000){ // subtask 2
int p, l, r;
if(s == 0) l = c[0], r = c[1];
else p = c[0], l = c[1], r = c.size() == 3 ? c[2] : -1;
if(t < s) return p;
else{
while(t > 0){
if((t - 1) / 2 == l) return l;
else if(r != -1 && (t - 1) / 2 == r) return r;
t = (t - 1) / 2;
}
return p;
}
}
else{ // subtask 3, 4, 5
int ssin, ssout, ttin, ttout;
ssin = s % 1000, ssout = s / 1000, ttin = t % 1000, ttout = t / 1000;
vector<int> tin(c.size(), 0), tout(c.size(), 0);
for(int i = 0; i < c.size(); i++) tin[i] = c[i] % 1000, tout[i] = c[i] / 1000;
for(int i = 0; i < c.size(); i++){
if(!ispar(tin[i], tout[i], ssin, ssout) && ispar(tin[i], tout[i], ttin, ttout)) return c[i];
}
for(int i = 0; i < c.size(); i++){
if(ispar(tin[i], tout[i], ssin, ssout)) return c[i];
}
return -1;
}
}
}
