#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);
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;
}
for(int i = 0; i<n; i++){
if(de[i] % 2) lb[i] = out[i];
else lb[i] = in[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;
}
// int main(void){
// freopen("input.txt", "r", stdin);
// int n; cin>>n;
// vector<int> u(n-1, 0);
// vector<int> v(n-1, 0);
// for(int i = 0; i<n-1; i++) cin>>u[i]>>v[i];
// label(n, 100000000, u, v);
// cout<<find_next_station(0, 18, {15, 27})<<endl;
// }
