#include "stations.h"
#include <bits/stdc++.h>
using namespace std;
void dfs(int u, int parent, int& num, vector<int>& enter, vector<int>& exit, vector<vector<int>>& adj){
enter[u] = num;
num++;
for(auto v : adj[u]){
if(v == parent) continue;
dfs(v, u, num, enter, exit, adj);
}
exit[u] = num;
num++;
}
vector<int> label(int n, int k, vector<int> u, vector<int> v) {
int N = n;
vector<vector<int>> adj(N);
vector<int> enter(N);
vector<int> exit(N);
for(int i = 0; i < N - 1; i++){
adj[u[i]].push_back(v[i]);
adj[v[i]].push_back(u[i]);
}
vector<int> labels(n);
int num = 0;
dfs(0, 0, num, enter, exit, adj);
for(int i = 0; i < N; i++){
string s = "";
string in = to_string(enter[i] + 1);
string out = to_string(exit[i] + 1);
while(out.size() < 4){
out = "0" + out;
}
s = in + out;
labels[i] = stoi(s);
}
return labels;
}
pair<int, int> convert(int s){
string ss = to_string(s);
int sIn = stoi(ss.substr(0, ss.size() - 4));
int sOut = stoi(ss.substr(ss.size() - 4, 4));
return {sIn, sOut};
}
int find_next_station(int s, int t, vector<int> c) {
if(c.size() == 1) return c[0];
auto [sIn, sOut] = convert(s);
auto [tIn, tOut] = convert(t);
for(auto child : c){
auto [cIn, cOut] = convert(child);
if(cIn < tIn && cOut > tOut){
return child;
}
}
for(auto child : c){
auto [cIn, cOut] = convert(child);
if(cIn < sIn && cOut > sOut){
return child;
}
}
return c[0];
}
// #include "stub.cpp"
