#include "stations.h"
#ifdef NYAOWO
#include "stub.cpp"
#endif
#include <bits/stdc++.h>
#define For(i, a, b) for(int i = a; i <= b; i++)
#define Forr(i, a, b) for(int i = a; i >= b; i--)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define sz(x) ((int)x.size())
#define eb emplace_back
// #define int LL
using namespace std;
using i32 = int32_t;
using LL = long long;
using pii = pair<int, int>;
const int MAXN = 1000;
vector<int> adj[MAXN + 10];
int ids[MAXN + 10];
int siz[MAXN + 10];
int cur_id;
void dfs1(int n, int p, int d) {
if(d) {
ids[n] = cur_id;
cur_id++;
}
siz[n] = 0;
for(auto &i:adj[n]) if(i != p) {
dfs1(i, n, 1 - d);
siz[n] += siz[i] + 1;
}
if(!d) {
ids[n] = cur_id;
cur_id++;
}
}
int encode(int id, int sz) {
return id * MAXN + sz;
}
int encode(pii p) {
return encode(p.F, p.S);
}
pii decode(int x) {
return pii(x / MAXN, x % MAXN);
}
std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
For(i, 0, n - 1) {
adj[i].clear();
}
int m = sz(u);
For(i, 0, m - 1) {
adj[u[i]].eb(v[i]);
adj[v[i]].eb(u[i]);
}
cur_id = 0;
dfs1(0, 0, 0);
vector<int> labels(n);
For(i, 0, n - 1) labels[i] = ids[i];
return labels;
}
int find_next_station(int s, int t, std::vector<int> c) {
if(sz(c) == 1) return c[0];
int n = sz(c);
if(s < c[0]) {
int p = c.back();
if(t <= s || t >= p) return p;
for(auto &i:c) if(t <= i) return i;
} else {
reverse(all(c));
int p = c.back();
if(t <= p || t >= s) return p;
for(auto &i:c) if(t >= i) return i;
}
return -1;
}
/*
1
5 10
0 1
1 2
1 3
2 4
2
2 0 1
1 3 3
*/
