#include "stations.h"
#include <bits/stdc++.h>
using namespace std;
int t = -1;
vector<vector<int>>adj;
vector<int>labels;
void DFS(int node,int parent,int odd)
{
if (odd)
{
t++;
labels[node] = t;
}
for (int child : adj[node]) {
if (child != parent) DFS(child,node,1 - odd);
}
if (!odd)
{
t++;
labels[node] = t;
}
}
vector<int> label(int n, int k, vector<int> u, vector<int> v)
{
adj.assign(n,{});
labels.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]);
}
t = -1;
DFS(0,t,1);
return labels;
}
int find_next_station(int s,int ta,vector<int> c)
{
if (c.empty()) return s;
sort(c.begin(), c.end());
if (s < c[0]) {
if (ta <= s) return c[c.size() - 1];
for (int i = 0; i < c.size(); i++)
{
if (ta <= c[i]) return c[i];
}
return c[c.size() - 1];
}
else
{
if (ta >= s) return c[0];
for (int i = c.size() - 1; i >= 0; i--)
{
if (ta >= c[i]) return c[i];
}
return c[0];
}
}
