#include "stations.h"
#include<bits/stdc++.h>
using namespace std;
#include <vector>
#define pb push_back
const int N = 5e5 + 5;
int n;
vector<int> Adj[N];
int l[N], r[N];
vector<int> vis;
void dfs(int u, int p){
l[u] = vis.size();
vis.pb(u);
for(auto v : Adj[u]){
if(v == p) continue;
dfs(v, u);
}
r[u] = vis.size();
}
//vector<int> vis;
int tol[1005][1005];
void prep(){
int cnt = 0;
for(int i = 0; i < n; i++){
for(int j = i + 1; j < n; j++){
tol[i][j] = cnt;
cnt++;
}
}
}
vector<int> label(int n_, int k, vector<int> u, vector<int> v) {
prep();
n = n_;
vis.clear();
for(int i = 0; i < n; i++) Adj[i].clear();
for(int i = 0; i < (n - 1); i++){
Adj[u[i]].pb(v[i]); Adj[v[i]].pb(u[i]);
}
dfs(0, 0);
vector<int> labels(n);
for(int i = 0; i < n; i++){
labels[i] = i;
}
return labels;
/*
std::vector<int> labels(n);
for (int i = 0; i < n; i++) {
labels[i] = i;
}
return labels;*/
}
bool anc(int x, int y){
//if(x == 0) return 1;
while(y){
y = (y - 1) / 2;
if(x == y) return 1;
}
return 0;
}
int find_next_station(int s, int t, std::vector<int> c) {
if(anc(c[0], t)) return c[0];
else if(anc(c[1], t)) return c[1];
else return (s - 1) / 2;
//return c[0];
}
