#include "stations.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
void dfs(int x, vector<int>& tin, vector<int>& tout, int& timer, vector<vector<int> >& adj, int p=-1) {
tin[x] = timer++;
for (auto y : adj[x]) {
if (y != p) dfs(y, tin, tout, timer, adj, x);
}
tout[x] = timer++;
}
void give_label(int x, vector<int>& labels, vector<vector<int> >& adj, vector<int>& tin, vector<int>& tout, 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, labels, adj, tin, tout, x, curr^1);
}
}
}
vector<int> label(int n, int k, vector<int> u, vector<int> v) {
vector<int> tin(1005);
vector<int> tout(1005);
vector<vector<int> > adj(1005, vector<int> (1005));
int timer = 0;
vector<int> labels(n);
for (int i=0; i < n-1; ++i) {
adj[u[i]].push_back(v[i]);
adj[v[i]].push_back(u[i]);
}
dfs(0, tin, tout, timer, adj);
give_label(0, labels, adj, tin, tout);
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];
}
}
}
