#include "stations.h"
#include <vector>
#include <iostream>
using namespace std;
#define ll long long
#define add push_back
#define len(a) ((int)(a).size())
vector<int> g[1005];
vector<int> labels;
int timer = 0;
void dfs(int v, int p, bool m){
if(m == 0) labels[v] = timer++;
for(int i = 0; i < len(g[v]); i++){
int to = g[v][i];
if(to == p) continue;
dfs(to, v, !m);
}
if(m == 1) labels[v] = timer++;
}
vector<int> label(int n, int k, vector<int> u, vector<int> v) {
labels.resize(n);
timer = 0;
for(int i = 0; i < n; i++) {
g[i].clear();
}
for(int i = 0; i < len(u); i++){
g[u[i]].add(v[i]);
g[v[i]].add(u[i]);
}
dfs(0, 0, false);
// for(int i = 0; i < n; i++){
// cout << labels[i] << " ";
// }
// cout << endl;
return labels;
}
int find_next_station(int s, int t, vector<int> c) {
// cout << s << " " << t << ": " << "\n";
// for(int i = 0; i < len(c); i++){
// cout << c[i] << " ";
// }
if(len(c) == 1){
return c[0];
}
int l, r;
if(s < c[0]){
l = s;
r = (s == 0 ? c[len(c) - 1] : c[len(c) - 2]);
if(!(l <= t && t <= r)){
// cout << len(c) - 1 << " ___ " << c[len(c) - 1] << endl;
return c[len(c) - 1];
}
int ind = (s == 0 ? len(c) - 1 : len(c) - 2);
while(ind >= 0 && t <= c[ind]){ ind--; }
// cout << ind + 1 << " __ " << c[ind + 1] << endl;
return c[++ind];
}
r = s;
l = c[1];
if(!(l <= t && t <= r)){
// cout << 0 << " " << c[0] << endl;
return c[0];
}
int ind = 1;
while(ind < len(c) && t >= c[ind]) { ind++; }
// cout << ind - 1 << " _ " << c[ind - 1] << endl;
return c[--ind];
}
