///
/// Standing here
/// I realize
/// You are just like me
/// Trying to make history
///
#include <bits/stdc++.h>
#define Loop(x,l,r) for(ll x = ll(l); x < ll(r); ++x)
#define LoopR(x,l,r) for(ll x = ll(r)-1; x >= ll(l); --x)
#define Kill(x) exit((cout << (x) << '\n', 0))
typedef long long ll;
typedef std::pair<int,int> pii;
typedef std::pair<ll,ll> pll;
using namespace std;
#ifndef LOCAL
#include "stations.h"
#endif
static const int N = 1010;
static vector<int> A[N];
static void dfs(int v, int p, int c, int &t, vector<int> &vec)
{
if (!c)
vec[v] = t++;
for (int u : A[v])
if (u != p)
dfs(u, v, !c, t, vec);
if (c)
vec[v] = t++;
}
vector<int> label(int n, int k, vector<int> u, vector<int> v)
{
vector<int> labels(n);
Loop (i,0,n)
A[i].clear();
Loop (i,0,n-1) {
A[v[i]].push_back(u[i]);
A[u[i]].push_back(v[i]);
}
int t = 0;
dfs(0, -1, 0, t, labels);
return labels;
}
int find_next_station(int s, int t, vector<int> c)
{
int l = 0, r = c.size();
if (s < c[0]) {
r -= !s; // excluding par
if (t < s) // left of this sub
return c.back();
auto it = lower_bound(c.begin()+l, c.begin()+r, t);
if (it == c.end()) // right of this sub
return c.back();
return *it;
} else {
l += 1; // excluding par
if (s < t) // rifht of this sub
return c.front();
auto it = upper_bound(c.begin()+l, c.begin()+r, t);
if (it == c.begin()) // left of this sub
return c.front();
return *--it;
}
}
#ifdef LOCAL
int main()
{
auto vec = label(5, 10, {0, 1, 1, 2}, {1, 2, 3, 4});
Loop (i,0,5)
cout << vec[i] << ' ';
cout << '\n';
auto a = A[2]; for (int &x : a) {x = vec[x];} sort(a.begin(), a.end());
cout << find_next_station(vec[2], vec[0], a) << '\n';
a = A[1]; for (int &x : a) {x = vec[x];} sort(a.begin(), a.end());
cout << find_next_station(vec[1], vec[3], a) << '\n';
cout << '\n';
a = A[0]; for (int &x : a) {x = vec[x];} sort(a.begin(), a.end());
cout << find_next_station(vec[0], vec[4], a) << '\n';
a = A[1]; for (int &x : a) {x = vec[x];} sort(a.begin(), a.end());
cout << find_next_station(vec[1], vec[4], a) << '\n';
a = A[2]; for (int &x : a) {x = vec[x];} sort(a.begin(), a.end());
cout << find_next_station(vec[2], vec[4], a) << '\n';
}
#endif
