#include "stations.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> AdjList[1005];
int dist[1005];
void dfs(int i, int k){
if(dist[i] != -1){return;}
dist[i] = k;
for(int v: AdjList[i]){
if(dist[v] == -1){
dfs(v, k+1);
return;
}
}
}
std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
std::vector<int> labels(n);
for(int i = 0; i < n; i ++){
AdjList[i].clear();
}
int s = -1;
memset(dist, -1, sizeof(dist));
for(int i = 0; i < n-1; i ++){
AdjList[u[i]].push_back(v[i]);
AdjList[v[i]].push_back(u[i]);
}
for(int i = 0; i < n; i ++){
if(AdjList[i].size() > 2){
s = i;
break;
}
}
if(s == -1){
for(int i = 0; i < n; i ++){
if(AdjList[i].size() == 1){
s = i;
break;
}
}
}
dist[s] = 0;
int cnt = 0;
for(int v: AdjList[s]){
dfs(v, 1000*cnt+1);
cnt ++;
}
for (int i = 0; i < n; i++) {
labels[i] = dist[i];
}
return labels;
}
int find_next_station(int s, int t, std::vector<int> c) {
//printf("s=%d t=%d\n", s, t);
assert(s != t);
if(s == 0){
return t/1000*1000+1;
}
if(s/1000 == t/1000){
if(s < t){
return s+1;
}else{
return s-1;
}
}else{
if(s%1000 == 1){
return 0;
}else{
return s-1;
}
}
/*for(int i = 1; i < 11; i ++){
if(s == (t>>i)){
return (t>>(i-1));
}
}
return s>>1;*/
}
