#include "stations.h"
#include <vector>
#include <iostream>
using namespace std;
void dfs(int v, int p, int type, int& cur, vector<int>& labels, vector<vector<int> >& adi)
{
if(type == 0)
{
labels[v] = cur;
cur ++;
}
for(int next : adi[v])
{
if(next == p) continue;
dfs(next, v, !type, cur, labels, adi);
}
if(type == 1)
{
labels[v] = cur;
cur ++;
}
cerr << v << " " << type << " " << labels[v] << '\n';
}
vector<int> label(int n, int k, vector<int> u, vector<int> v) {
vector<int> labels(n, -1);
vector<vector<int> > adi(n);
for(int i = 0; i < n - 1; i ++)
{
adi[u[i]].push_back(v[i]);
adi[v[i]].push_back(u[i]);
}
int cur = 0;
dfs(0, -1, 0, cur, labels, adi);
return labels;
}
int find_next_station(int s, int t, vector<int> c)
{
int ans;
if(c[0] > s)
{
if(t < s) ans = c.back();
else
{
int lo = -1, hi = c.size() - 1;
while(lo + 1 < hi)
{
int m = (hi + lo) / 2;
if(c[m] >= t) hi = m;
else lo = m;
}
ans = c[hi];
}
}
else
{
if(t > s) ans = c[0];
else
{
int lo = 0, hi = c.size();
while(lo + 1 < hi)
{
int m = (hi + lo) / 2;
if(c[m] > t) hi = m;
else lo = m;
}
ans = c[lo];
}
}
//cerr << ans << '\n';
return ans;
}
