#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];
void dfs(int n, int p) {
static int cur_id = 0;
ids[n] = cur_id;
cur_id++;
siz[n] = 0;
for(auto &i:adj[n]) if(i != p) {
dfs(i, n);
siz[n] += siz[i] + 1;
}
}
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]);
}
dfs(0, 0);
vector<int> labels(n);
For(i, 0, n - 1) {
labels[i] = encode(ids[i], siz[i]);
}
return labels;
}
int find_next_station(int s, int t, std::vector<int> c) {
if(sz(c) == 1) return c[0];
vector<pii> v; // {id, sz}
for(auto &x:c) v.eb(decode(x));
sort(all(v));
int n = sz(v);
int id = v[1].F - 1;
int sz = 0;
For(i, 1, n - 1) sz += v[i].S + 1;
pii pt = decode(t);
if(pt.F < id || pt.F > id + sz) return encode(v[0]);
For(i, 1, n - 2) {
if(pt.F < v[i + 1].F) return encode(v[i]);
}
return encode(v[n - 1]);
}
/*
1
5 10
0 1
1 2
1 3
2 4
2
2 0 1
1 3 3
*/
