#include <bits/stdc++.h>
#include "stub.cpp"
using namespace std;
#include "stations.h"
int id;
vector<vector<int>>adj;
vector<int>labels;
void dfs(int v, int p, int d) {
if(!d)labels[v]=id++;
for(auto u:adj[v]){
if(u==p)continue;
dfs(u,v,d^1);
}
if(d)labels[v]=id++;
}
vector<int>label(int n,int k,vector<int>u,vector<int>v){
labels.assign(n,-1);
adj.assign(n,{});
id=0;
for(int i=0;i<u.size();i++)adj[u[i]].push_back(v[i]),adj[v[i]].push_back(u[i]);
dfs(0,0,0);
return labels;
}
int find_next_station(int s,int t,vector<int>c){
if(s<c[0]){
if(t<s||t>=c.back())return c.back();
return *lower_bound(c.begin(),c.end(),t);
}
if(t>s||t<=c[0])return c[0];
return *--upper_bound(c.begin(),c.end(),t);
return c[0];
}