#include <iostream>
#include <vector>
#include <algorithm>
#include <math.h>
#include "stations.h"
using namespace std;
vector<vector<int>> adj;
vector<int> lb;
vector<int> de;
int ti = 0;
vector<int> in;
vector<int> out;
vector<int> vis;
vector<int> eulerTour;
void dfs(int st, int d){
de[st] = d;
vis[st] = 1;
eulerTour.push_back(st);
ti++;
for(auto i : adj[st]){
if(!vis[i]){
dfs(i, d+1);
eulerTour.push_back(st);
}
}
}
vector<int> label (int n, int k, vector<int> u, vector<int> v){
ti = 0;
adj.assign(n, {});
in.assign(n, -1);
out.assign(n, -1);
vis.assign(n, 0);
eulerTour.clear();
for(int i = 0; i<n-1; i++){
adj[u[i]].push_back(v[i]);
adj[v[i]].push_back(u[i]);
}
lb.assign(n, -1);
de.assign(n, -1);
dfs(0, 0);
for(int i = 0; i<eulerTour.size(); i++){
if(in[eulerTour[i]] == -1) in[eulerTour[i]] = i;
out[eulerTour[i]] = i;
}
vector<pair<int, int>> com(n, pair<int, int>(-1, -1));
for(int i = 0; i<n; i++){
if(de[i] % 2) com[i] = {out[i], i};
else com[i] = {in[i], i};
}
sort(com.begin(), com.end());
for(int i = 0; i<n; i++){
lb[com[i].second] = i;
}
return lb;
}
int subtree(int par, int u){
return 0;
}
int find_next_station(int s, int t, vector<int> c){
int i = -1, o = -1;
if(s == 0){
for(int i = 0; i<c.size(); i++){
if(c[i] >= t) return c[i];
}
return -1;
}
if(s > c[0]){
if(c.size() == 1) return c[0];
if(s < t) return c[0];
for(int i = c.size()-1; i>0; i--){
if( c[i] <= t ) return c[i];
}
return c[0];
}
else{
if(c.size() == 1) return c[0];
if( t < s || c[c.size()-2] < t) return c[c.size()-1];
for(int i = 0; i<c.size()-1; i++){
if(s <= t && t <= c[i]) return c[i];
}
return c[c.size()-1];
}
return -1;
}
