#include "stations.h"
#include <bits/stdc++.h>
using namespace std;
#define all(l) l.begin(),l.end()
#define pb push_back
// vector<int> labels,vis;
// vector<vector<int>>adj;
// int t = 0;
void dfs(int y,int p,vector<int>&vis,vector<int>&labels,vector<vector<int>>&adj,int &t){
if(p == 0)
labels[y] = t;
t++;
for(int i:adj[y]){
if(!vis[i]){
vis[i] = 1;
dfs(i,p^1,vis,labels,adj,t);
t++;
}
}
if(p == 1){
labels[y] = --t;
}
}
vector<int> label(int n, int k,vector<int> u, vector<int> v) {
vector<int> labels,vis;
vector<vector<int>>adj;
labels.resize(n,0);
adj.resize(n+1);
vis.resize(n+1,0);
for(int i = 0;i<n-1;i++){
adj[u[i]].push_back(v[i]);
adj[v[i]].push_back(u[i]);
}
int t = 0;
vis[0] = 1;
dfs(0,0,vis,labels,adj,t);
vector<vector<int>>ord;
for(int i = 0;i<n;i++)ord.pb({labels[i],i});
sort(all(ord));
t = 0;
for(auto i:ord){
labels[i[1]] = t;
t++;
}
return labels;
}
int find_next_station(int s, int t, vector<int> c) {
sort(all(c));
int n = c.size();
if(n == 1){
return c[0];
}
if(c[0] > s){
if(s > t){
return c.back();
}
else{
for(int i = 0;i<n-1;i++){
if(c[i] >= t){
return c[i];
}
}
}
}
else{
if(s < t){
return c[0];
}
else{
for(int i = n-1;i>0;i--){
if(c[i] <= t){
return c[i];
}
}
}
}
return c[0];
}
// int main(){
// freopen("inp.in","r",stdin);
// freopen("out.in","w",stdout);
// vector<int>ans = label(9,10,{0,1,1,2,2,4,6,6},{1,2,3,4,5,6,7,8});
// for(int i:ans){
// cout<<i<<" ";
// }
// cout<<endl;
// cout<<find_next_station(1,2,{5,6})<<endl;
// }
