#include "stations.h"
#include <vector>
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a;i<b;i++)
#define trav(a,v) for(auto a:v)
typedef long long int lld;
vector<int> nei[100000];
int L[100000];
int R[100000];
int cnt;
bool visited[100000];
bool parity[1000000];
void DFS(int node){
visited[node]=true;
L[node]=cnt;
cnt++;
trav(a,nei[node]){
if(!visited[a]){
parity[a]=1^parity[node];
DFS(a);
}
}
R[node]=cnt-1;
}
std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
rep(i,0,n)nei[i].clear();
rep(i,0,(int)u.size()){
nei[u[i]].push_back(v[i]);
nei[v[i]].push_back(u[i]);
}
cnt=0;
rep(i,0,n)visited[i]=false;
parity[0]=false;
DFS(0);
vector<pair<pair<int,int>,pair<int,int> > >V(n);
rep(i,0,n){
V[i]={{(parity[i] ? R[i] : L[i]),parity[i]},{-L[i],i}};
}
sort(V.begin(),V.end());
/*rep(i,0,n){
cout<<R[V[i].second.second]<<endl;
cout<<V[i].first.first<<" "<<V[i].first.second<<" "<<V[i].second.first<<" "<<V[i].second.second<<endl;
}*/
vector<int> answer(n);
rep(i,0,n)answer[V[i].second.second]=i;
//rep(i,0,n)cout<<answer[i]<<endl;
return answer;
}
int find_next_station(int s, int t, std::vector<int> c) {
sort(c.begin(),c.end());
if(c[c.size()-1]<s){
//parity=R
int L=c[1];
int R=s;
if(t<L || R<t){
return c[0];
}
int best=1000000;
trav(a,c){
if(a>=t)best=min(best,a);
}
return best;
}
//parity=L
reverse(c.begin(),c.end());
int L=s;
int R=c[1];
if(t<L || R<t)return c[0];
int best=-1;
trav(a,c){
if(a<=t)best=max(best,a);
}
return best;
}
