#include "stations.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
void dfs(int cur, bool color, int &timer, vector<int> &res, vector<bool> &vis, vector<vector<int> > &g) {
vis[cur] = true;
if(color) {
timer++;
res[cur] = timer;
}
for(int nei : g[cur]) {
if(!vis[nei]) {
dfs(nei, !color, timer, res, vis, g);
}
}
if(!color) {
timer++;
res[cur] = timer;
}
}
vector<int> label(int n, int k, vector<int> u, vector<int> v) {
int timer = 0;
vector<int> res(n, 0);
vector<bool> vis(n, false);
vector<vector<int> > g(n);
for(int i = 0; i < n - 1; i++) {
g[u[i]].pb(v[i]);
g[v[i]].pb(u[i]);
}
dfs(0, true, timer, res, vis, g);
/*for(int x : res) {
cout << x << " ";
}
cout << "\n";*/
return res;
}
#define ans(x) int tmp = (to_swap ? ceil - x : x); /*cout << "Answer: " << tmp << "\n";*/ return tmp;
int find_next_station(int s, int t, vector<int> c) {
/*cout << "Question:\n";
cout << s << " " << t << "\n";
for(int x : c) {
cout << x << " ";
}
cout << "\n";*/
if(s == 1) {
for(int &x : c) {
if(t <= x) {
//cout << "Answer: " << x << "\n";
return x;
}
}
}
bool to_swap = false;
int ceil = max({s, t, *max_element(c.begin(), c.end())}) + 1;
if(c[0] < s) {
to_swap = true;
s = ceil - s;
t = ceil - t;
for(int &x : c) {
x = ceil - x;
}
reverse(c.begin(), c.end());
}
int p = c.back();
c.resize((int) c.size() - 1);
if(t < s) {
ans(p);
}
for(int &x : c) {
if(t <= x) {
ans(x);
}
}
ans(p);
}
