#include "stations.h"
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair < int, int > pii;
typedef pair < ll, ll > pll;
#define endl "\n"
#define F first
#define S second
#define Mp make_pair
#define all(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
#define fast_io ios::sync_with_stdio(0);cin.tie(0);cout.tie()
const int N = 1e3 + 10;
const int LOG = 20;
const ll mod = 1e9 + 7;
const ll inf = 8e18;
int ptr = -1, H[N], St[N], Fi[N];
vector < int > G[N];
void dfs(int v, int P = -1)
{
St[v] = ++ ptr;
for(auto u : G[v])
{
if(u == P) continue;
H[u] = H[v] + 1;
dfs(u, v);
}
Fi[v] = ++ ptr;
}
vector < int > label(int n, int k, vector < int > A, vector < int > B)
{
ptr = -1;
for(int i = 0; i < n; i ++)
{
H[i] = 0;
G[i].clear();
St[i] = Fi[i] = 0;
}
vector < int > ret(n);
for(int i = 0; i < n - 1; i ++)
{
G[A[i]].push_back(B[i]);
G[B[i]].push_back(A[i]);
}
dfs(0, -1);
for(int i = 0; i < n; i ++)
{
if(H[i] & 1)
{
ret[i] = Fi[i];
}
else
{
ret[i] = St[i];
}
}
/*for(int i = 0; i < n; i ++)
{
printf("%d ", ret[i]);
}
printf("\n");*/
return ret;
}
int find_next_station(int s, int t, vector < int > c)
{
int sz = SZ(c);
sort(all(c));
int tp = 1;
for(auto u : c)
{
if(u > s) tp = 0;
}
if(s == 0)
{
int id = lower_bound(all(c), t) - c.begin();
return c[id];
}
if(tp == 0)
{
if(t < s) return c.back();
int id = lower_bound(all(c), t) - c.begin();
if(id <= sz - 2)
{
return c[id];
}
return c.back();
}
if(t > s) return c[0];
if(t <= c[0]) return c[0];
int id = upper_bound(all(c), t) - c.begin() - 1;
return c[id];
}
