#include"stations.h"
#include<vector>
#include<iostream>
#include<algorithm>
using namespace std;
vector<int>labels;
int n;
vector<int>nodes[1000];
int curr_label;
void dfs(int node,int par,bool pr){
if(pr)
labels[node]=curr_label++;
for(int ne:nodes[node]){
if(ne==par)
continue;
dfs(ne,node,!pr);
}
if(!pr)
labels[node]=curr_label++;
}
vector<int>label(int N,int k,vector<int>u,vector<int>v){
n=N;
labels.resize(n);
for(int i=0;i<n;i++)
nodes[i].clear();
curr_label=0;
for(int i=0;i<n-1;i++){
nodes[u[i]].push_back(v[i]);
nodes[v[i]].push_back(u[i]);
}
dfs(0,0,false);
return labels;
}
int find_next_station(int s,int t,vector<int>c){
sort(c.begin(),c.end());
/*cout<<"s "<<s<<endl;
cout<<"t "<<t<<endl;
cout<<"arr ";
for(int i:c)
cout<<i<<" ";
cout<<endl;*/
if(c.size()==1)
return c[0];
if(s<c[0]){
// s is smaller that everyhting on its subtree
if(t<s||t>c.back()) // target is not in subtree
return c.back(); // the biggest is the root then
// it must be in one of the children
for(int i=0;i<(int)c.size()-1;i++){
if(c[i]<t&&t<=c[i+1])
return c[i+1];
}
return c[0];
}else{
// s is bigger that everything on its subtree
if(t>s||t<c[0]) // target is not in subtree
return c[0]; // the biggest is the root then
// it must be in one of the children
for(int i=0;i<(int)c.size()-1;i++){
if(c[i]<=t&&t<c[i+1])
return c[i];
}
return c.back();
}
}
