#include "bits/stdc++.h"
#include "stations.h"
using namespace std;
int tt;
void dfs(int node , vector<int>& lab , vector<vector<int>>& graph , bool dip , vector<int> &vis)
{
if(dip == 0)
lab[node] = tt;
tt++;
vis[node] = 1;
for(auto i : graph[node])
{
if(vis[i] == 0)
dfs(i , lab , graph , dip ^ 1 , vis);
}
if(dip == 1)
lab[node] = tt;
tt++;
}
vector<int> label(int n, int k, vector<int> u, vector<int> v)
{
vector<vector<int>> graph(n + 5);
for(int i = 0 ; i < n - 1 ; i++)
{
graph[u[i]].push_back(v[i]);
graph[v[i]].push_back(u[i]);
}
vector<int> lab(n + 5) , vis(n + 5);
dfs(0 , lab , graph , 0 , vis);
return lab;
}
int find_next_station(int s, int t, vector<int> c)
{
if(c.size() == 1)
return c[0];
if(s < c[0])
{
/// start
int p = -1;
for(int i = 0 ; i < c.size() - 1 ; i++)
{
int st , en = c[i];
if(p == -1)
st = s + 1;
else
st = p + 1;
if(st <= t && t <= en)
return c[i];
p = c[i];
}
return c.back();
}
/// end
int p = -1;
for(int i = c.size() - 1 ; i >= 1 ; i--)
{
int st = c[i] , en;
if(p == -1)
en = s - 1;
else
en = p - 1;
if(st <= t && t <= en)
return c[i];
p = c[i];
}
return c[0];
}
