#include "stations.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> g[200001];
int in[200001],out[200001];
int d[200001];
vector<int> l;
pair<int,int> h[200001];
int num;
void dfs(int i,int p)
{
in[i]=num++;
for(int j=0;j<g[i].size();j++)
{
int nb=g[i][j];
if(nb==p)continue;
d[nb]=d[i]+1;
dfs(nb,i);
}
out[i]=num++;
if(d[i]%2==0)l[i]=in[i];
else l[i]=out[i];
}
std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v)
{
num=0;
l.clear();
for(int i=0;i<n;i++)
l.push_back(0);
for(int i=0; i<n; i++)
g[i].clear();
for(int i=0; i<n-1; i++)
g[u[i]].push_back(v[i]),g[v[i]].push_back(u[i]);
dfs(0,-1);
for(int i=0;i<n;i++)
h[i].first=l[i],h[i].second=i;
sort(h,h+n);
for(int i=0;i<n;i++)
l[h[i].second]=i;
return l;
}
int find_next_station(int s, int t, std::vector<int> c)
{
if(s==0)
{
for(int i=0;i<c.size();i++)
{
if(t<=c[i])return c[i];
}
}
if(s<c[0])
{
for(int i=0;i<c.size()-1;i++)
{
int lf=s;
if(i!=0)lf=c[i-1];
if(lf<t&&t<=c[i])return c[i];
}
return c[c.size()-1];
}
for(int i=c.size()-1;i>0;i--)
{
int rt=s;
if(i!=c.size()-1)rt=c[i+1];
if(c[i]<=t&&t<rt)return c[i];
}
return c[0];
}
