#include "stations.h"
#include <vector>
#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#define pb push_back
#define F first
#define pii pair<ll,ll>
#define all(a) a.begin(),a.end()
#define S second
#define sz(a) (int)a.size()
#define rep(i , a , b) for(int i = (a) ; i <= (b) ; i++)
#define per(i , a , b) for(int i = (a) ; i >= (b) ; i--)
#define ld double
#define ll long long
using namespace std ;
const int maxn = 1e6 + 10 , maxm = 4000 + 10 , maxh = 400 + 10 , lg = 25 , maxk = 100 + 10 , inf = 1e9+ 10 , mod = 1e9 + 9 ;
int cnt =0 , id[maxn];
vector <int> G[maxn] ;
void dfs(int v, int d = 0 , int par =-1){
if(d==0){
id[v] = cnt ;cnt++;
}
for(int u : G[v]){
if(u == par)continue ;
dfs(u , d^1 , v);
}
if(d==1){
id[v] = cnt ; cnt++ ;
}
}
std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
rep(i , 0 , n)G[i].clear() ;
cnt =0 ;
rep(i , 0 , n-2){
G[v[i]].pb(u[i]);
G[u[i]].pb(v[i]);
}
dfs(0, 0);
vector <int> ans ;
rep(i , 0 ,n-1)ans.pb(id[i]) ;
return ans ;
}
int find_next_station(int s, int t, std::vector<int> c) {
// cout << s << " " << t << " : " ;
// for(int x : c)cout << x << " ";
// cout << "\n";
if(s==0){
int x = lower_bound(all(c) , t) - c.begin() ;
return c[x];
}
if(s < c[0]){
int par = c.back();
c.pop_back();
if(sz(c)==0)return par ;
if(t >= s && t <= c.back()){
int x= lower_bound(all(c) , t) - c.begin() ;
return c[x];
}else{
return par;
}
}else{
int par = c[0] ;
vector <int> c2 ;
rep(i , 1 ,sz(c)-1){
c2.pb(c[i]) ;
}
c= c2 ;
if(sz(c) == 0)return par ;
if(t >= c[0] && t <= s){
int x =lower_bound(all(c) , t+1) - c.begin()-1 ;
return c[x] ;
}else{
return par ;
}
}
return -1;
}
