#include "stations.h"
#include <bits/stdc++.h>
using namespace std;
#define MAXN 200001
#define nl '\n'
#define ff first
#define ss second
#define ll long long
#define ld long double
#define terminator main
#define pll pair<ll,ll>
#define add insert
#define append push_back
#define pii pair<int,int>
#define all(x) (x).begin(),(x).end()
bool p[MAXN];
int siz[MAXN];
bool vis[MAXN];
vector<int> et;
vector<int> a[MAXN];
void dfs(int v){
et.append(v);
siz[v] = vis[v] = 1;
for(auto & i : a[v]){
if(vis[i]) continue;
p[i] = 1 - p[v];
dfs(i);
siz[v] += siz[i];
}
}
vector<int> label(int n, int k, vector<int> u, vector<int> v) {
vector<int> x, l(n, -1);
for(int i = 0; i < n; i++){
p[i] = vis[i] = 0;
a[i].clear();
x.append(i);
}
et.clear();
for(int i = 0; i < n - 1; i++){
a[u[i]].append(v[i]);
a[v[i]].append(u[i]);
x.append(i);
}
dfs(0);
for(auto & i : et){
if(p[i]){
l[i] = x[siz[i] - 1];
for(int j = siz[i] - 1; j < x.size() - 1; j++)
x[j] = x[j + 1];
x.pop_back();
}
else{
l[i] = x[0];
for(int j = 0; j < x.size() - 1; j++)
x[j] = x[j + 1];
x.pop_back();
}
}
return l;
}
int find_next_station(int s, int t, vector<int> c){
if(c[0] > s){
if(c.back() < t || t < s)
return c.back();
return *lower_bound(all(c), t);
}
if(c[0] > t || t > s) return c[0];
return *(--upper_bound(all(c), t));
}
