#include "stations.h"
#include <bits/stdc++.h>
using namespace std;
constexpr int N = (int)1e3;
int tin[N],tout[N];
int timer = 0;
vector<int> g[N];
int id[N];
int d[N];
int c = 0;
vector<int> labels;
mt19937 rnd(time(nullptr));
void dfs(int v,int pr = -1){
tin[v] = timer++;
for(auto& to : g[v]){
if(to == pr) continue;
if(id[v] == 0)
id[to] = ++c;
else
id[to] = id[v];
d[to] = d[v] + 1;
dfs(to,v);
}
tout[v] = timer++;
if(d[v] % 2 == 0){
labels[v] = (tin[v] << 1);
} else {
labels[v] = (tout[v] << 1) | 1;
}
return;
}
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();
timer = 0;
labels.clear();
labels.resize(n);
memset(id,0,sizeof id);
memset(d,0,sizeof d);
c = 0;
for(int i = 0; i < n-1; i++){
g[u[i]].push_back(v[i]);
g[v[i]].push_back(u[i]);
}
int root = 0;
for(int i = 0; i < n; i++) if(g[i].size() < g[root].size()) root = i;
d[root] = -1;
dfs(root);
return labels;
}
bool upper(int a,int b){
return tin[a] <= tin[b] && tout[a] >= tout[b];
}
int find_next_station(int s, int t, std::vector<int> c) {
int tinS = 2*N, toutS = -1, tinT = 2*N, toutT = -1;
if(s & 1)
toutS = s >> 1;
else
tinS = s >> 1;
if(t & 1)
toutT = t >> 1;
else
tinT = t >> 1;
int pr = -1;
for(auto& to : c){
int in,out;
if(to & 1){
out = to >> 1;
if(pr == -1 || out > (pr >> 1))
pr = to;
}
else{
in = to >> 1;
if(pr == -1 || in < (pr >> 1))
pr = to;
}
}
int go = -1;
for(auto& to : c){
if(to == pr) continue;
int in,out;
if(to & 1){
out = to >> 1;
if(t & 1){ /// toutT
if(out >= toutT && (go == -1 || out < (go >> 1)))
go = to;
} else { /// tinT
if(tinT < tinS)
return pr;
if(out >= tinT && (go == -1 || out < (go >> 1)))
go = to;
}
}
else{
in = to >> 1;
if(t & 1){ /// toutT
if(toutT > toutS)
return pr;
if(in <= toutT && (go == -1 || in > (go >> 1)))
go = to;
} else { /// tinT
if(in <= tinT && (go == -1 || in > (go >> 1)))
go = to;
}
}
}
if(go == -1)
return pr;
return go;
}
