#include "stations.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
int tin[1005];
int tout[1005];
vector<int> adj[1005];
int timer;
vector<int> labels;
void dfs(int x, int p=-1) {
tin[x] = timer++;
for (auto y : adj[x]) {
if (y != p) dfs(y, x);
}
tout[x] = timer++;
}
void give_label(int x, int p=-1, int curr=0) {
labels[x] = (curr==0)?(tin[x]):(tout[x]);
for (auto y : adj[x]) {
if (y != p) {
give_label(y, x, curr^1);
}
}
}
vector<int> label(int n, int k, vector<int> u, vector<int> v) {
labels.resize(n);
timer = 0;
for (int i=0; i < n-1; ++i) {
adj[u[i]].push_back(v[i]);
adj[v[i]].push_back(u[i]);
}
dfs(0);
give_label(0);
return labels;
}
int find_next_station(int s, int t, vector<int> c) {
if ((int)c.size() == 1) {
return c[0];
}
else if (s > c[(int)c.size()-1]) { //Then s is exit time
if (t > s) {
return c[0];
}
else {
for (int i=1; i < (int)c.size()-1; ++i) {
if (c[i] < t && t < c[i+1]) {
return c[i];
}
}
return c[(int)c.size()-1];
}
}
else {
if (c[(int)c.size()-2]+1 < t) {
return c[(int)c.size()-1];
}
else {
for (int i=1; i < (int)c.size(); ++i) {
if (c[i-1] < t && t < c[i]) {
return c[i];
}
}
return c[0];
}
}
}
