#include "stations.h"
#include <vector>
#include <algorithm>
using namespace std;
vector<int> adj[1000];
vector<int> labels;
int sub[1000];
void dfs1(int x, int p)
{
sub[x] = 1;
for(int i : adj[x])
{
if(i == p) continue;
dfs1(i, x);
sub[x] += sub[i];
}
}
void dfs2(int x, int p, int d, int l, int r){
if(d == 0) labels[x] = l;
else labels[x] = r;
int tmp = l;
if(d == 0) tmp = l + 1;
for(int i : adj[x])
{
if(i == p) continue;
dfs2(i, x, !d, tmp, tmp + sub[i] - 1);
tmp += sub[i];
}
}
vector<int> label(int n, int k, vector<int> u, vector<int> v) {
labels.resize(n);
for(int i=0;i<n;i++) adj[i].clear();
for(int i=0;i<n-1;i++){
adj[u[i]].push_back(v[i]);
adj[v[i]].push_back(u[i]);
}
dfs1(0, -1);
dfs2(0, -1, 0, 0, n-1);
return labels;
}
int find_next_station(int s, int t, std::vector<int> c) {
int k = c.size() - 1;
int m = c[0], M = c[k];
if(m > s)
{
if(t < s) return M;
for(int i=0;i<k;i++)
{
if(t <= c[i]) return c[i];
}
return M;
}
if(t > s) return m;
for(int i=k;i>0;i--)
{
if(t >= c[i]) return c[i];
}
return m;
}
