#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
using namespace std;
using ll = long long;
using ld = long double;
//#define int ll
#define sz(x) ((int)(x).size())
using pii = pair<int,int>;
using tii = tuple<int,int,int>;
const int nmax = 1e3 + 5;
vector<int> g[nmax];
int pin[nmax], pout[nmax], d[nmax];
int p = 0;
void dfs(int node, int f) {
pin[node] = p++;
d[node] = d[f] ^ 1;
//cerr << node << ' ' << f << '\n';
for(auto x : g[node])
if(x != f) dfs(x, node);
pout[node] = p++;
}
std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
for(int i = 0; i < n; i++) g[i].clear();
p = 0;
for(int i = 0; i < sz(u); i++)
g[u[i]].emplace_back(v[i]),
g[v[i]].emplace_back(u[i]);
dfs(0, 0);
vector<int> rez(n);
for(int i = 0; i < n; i++)
rez[i] = (d[i]? pin[i] : pout[i]);
map<int, int> freq;
int cnt = 0;
for(auto x : rez) freq[x];
for(auto &[a, b] : freq) b = cnt++;
for(auto &x : rez) x = freq[x];
//for(int i = 0; i < n; i++) cerr << i << " --> " << rez[i] << '\n';
return rez;
}
int find_next_station(int s, int t, std::vector<int> c) {
if(sz(c) == 1) return c[0];
if(s < c[0]) {
//cerr << s << " --> " << t << '\n';
//for(auto x : c) cerr << x << ' ';
//cerr << '\n';
if(t < s || rbegin(c)[1] < t) return c.back();
for(int i = 0; i < sz(c); i++)
if(t <= c[i]) return c[i];
//assert(true == false);
}
else {
if(t > s || t < c[1]) return c[0];
int n = sz(c);
c.emplace_back(s);
for(int i = 1; i < n; i++) {
if(c[i] <= t && t < c[i + 1]) return c[i];
}
//cerr << s << ' ' << t << '\n';
//c.pop_back();
//for(auto x : c) cerr << x << ' ';
//cerr << '\n';
//assert(true == false);
}
assert(false);
}
/**
Anul asta se da centroid.
-- Surse oficiale
*/
