#include "stations.h"
#include<bits/stdc++.h>
using namespace std;
const int MAX_SOM=1005;
int dv[MAX_SOM];
vector<int> adja[MAX_SOM];
vector<int> ordre;
void DFS(int pos,int prof) {
if (dv[pos]==0) {
dv[pos]=1;
if (prof%2==0) {
ordre.push_back(pos);
}
for (int j:adja[pos]) {
DFS(j,prof+1);
}
if (prof%2==1) {
ordre.push_back(pos);
}
}
}
vector<int> label(int n,int k,vector<int> u,vector<int> v) {
int nbSom=n;
for (int i=0;i<nbSom;i++) {
adja[i].clear();
dv[i]=0;
}
ordre.clear();
for (int i=0;i<nbSom-1;i++) {
adja[u[i]].push_back(v[i]);
adja[v[i]].push_back(u[i]);
}
DFS(0,0);
vector<int> label(nbSom);
for (int i=0;i<nbSom;i++) {
label[ordre[i]]=i;
}
/*for (int i=0;i<nbSom;i++) {
cout<<i<<" : "<<label[i]<<endl;
}*/
return label;
}
int find_next_station(int pos,int obj,vector<int> possi) {
if (possi.size()==1) {
return possi[0];
}
vector<int> inf,sup;
for (int i:possi) {
if (i<pos) {
inf.push_back(i);
}
else {
sup.push_back(i);
}
}
if (pos==0) {
for (int i:sup) {
if (i>=obj) {
return i;
}
}
}
if (inf.empty()) {
for (int i=0;i<(int)sup.size()-1;i++) {
if (sup[i]>=obj and pos<obj) {
return sup[i];
}
}
return sup.back();
}
else {
for (int i=(int)inf.size()-1;i>0;i--) {
if (inf[i]<=obj and pos>obj) {
return inf[i];
}
}
return inf[0];
}
}
