#include "stations.h"
#include <vector>
#include <cmath>
#include <iostream>
#include <algorithm>
using namespace std;
vector<vector<int>> adj;
vector<int> L, R, lvl;
int ind;
void dfs(int x) {
L[x]=ind++;
for(auto i:adj[x]) {
if(!L[i]) {
lvl[i]=lvl[x]+1;
dfs(i);
}
}
R[x]=ind++;
}
std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
adj.resize(n);
for(auto& i:adj) i.clear();
for(int i=0;i<n-1;++i) {
adj[u[i]].push_back(v[i]);
adj[v[i]].push_back(u[i]);
//~ cerr<<u[i]<<" "<<v[i]<<"\n";
}
L.assign(n, 0);
R.assign(n, 0);
lvl.assign(n, 0);
ind=1;
dfs(0);
std::vector<int> labels(n);
for (int i = 0; i < n; i++) {
labels[i] = lvl[i]&1?L[i]:R[i];
//~ std::cerr<<i<<"("<<lvl[i]<<")"<<" ";
}
//~ cerr<<"\n";
vector<int> s(labels.begin(), labels.end());
sort(s.begin(), s.end());
for(int i=0;i<n;++i) labels[i]=lower_bound(s.begin(), s.end(), labels[i])-s.begin();
//~ for(auto i:labels) cerr<<i<<" ";cerr<<"\n";
return labels;
}
bool contains(int a, int b, int x) {
return min(a, b)<=x && x<=max(a, b);
}
int find_next_station(int s, int t, std::vector<int> c) {
int best=-1;
for(int i:c) {
if(contains(s, i, t)) {
if(best==-1 || abs(best-s)>abs(s-i)) best=i;
}
}
if(best==-1) {
for(int i:c) {
if(best==-1 || abs(best-s)<abs(s-i)) best=i;
}
}
return best;
}
