#include "stations.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10;
int n , tim , st_tim[N] , fn_tim[N] , dis[N];
vector <int> adj[N];
void Dfs(int v , int p = -1)
{
st_tim[v] = tim;
tim++;
for(auto u : adj[v]) if(u != p)
{
dis[u] = (dis[v] ^ 1);
Dfs(u , v);
}
fn_tim[v] = tim;
tim++;
}
vector<int> label(int nn, int k, vector<int> u, vector<int> v) {
n = nn;
for(int i = 0 ; i < n ; i++)
{
dis[i] = 0;
adj[i].clear();
}
tim = 0;
for(int i = 0 ; i < n - 1 ; i++)
{
adj[u[i]].push_back(v[i]);
adj[v[i]].push_back(u[i]);
}
int root = -1;
for(int i = 0 ; i < n ; i++) if(adj[i].size() == 1)
root = i;
Dfs(root);
vector <int> all;
for(int i = 0 ; i < n ; i++)
{
if(dis[i] == 0)
all.push_back(st_tim[i]);
else
all.push_back(fn_tim[i]);
}
sort(all.begin() , all.end());
vector<int> labels(n);
for (int i = 0; i < n; i++)
{
if(dis[i] == 0)
labels[i] = lower_bound(all.begin() , all.end() , st_tim[i]) - all.begin();
else
labels[i] = lower_bound(all.begin() , all.end() , fn_tim[i]) - all.begin();
}
return labels;
}
int find_next_station(int s, int t, vector<int> c) {
if(c.size() == 1)
return c[0];
if(c[0] > s)
{
int par = c.back();
c.pop_back();
int mn = s , mx = c.back();
if(t < mn || t > mx)
return par;
int ans = N;
for(auto u : c) if(t <= u)
{
ans = u;
break;
}
return ans;
}
else
{
int par = c[0];
int mn = c[1] , mx = s;
if(t < mn || t > mx)
return par;
int ans = N;
for(int i = c.size() - 1 ; i > 0 ; i--) if(c[i] <= ans)
{
ans = c[i];
break;
}
return ans;
}
}
