#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];
void DFS(int node){
visited[node]=true;
L[node]=cnt;
cnt++;
trav(a,nei[node]){
if(!visited[a]){
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;
DFS(0);
vector<int> answer(n);
rep(i,0,n)answer[i]=R[i]*1000+L[i];
//rep(i,0,n)cout<<L[i]<<" "<<R[i]<<endl;
//rep(i,0,n)cout<<answer[i]<<endl;
return answer;
}
int contain(int a, int b, int c, int d){
if(a<=c && d<=b)return -1;
if(c<=a && b<=d)return 1;
return 0;
}
int find_next_station(int s, int t, std::vector<int> c) {
int sL=s%1000;
int sR=s/1000;
int tL=t%1000;
int tR=t/1000;
//cout<<sL<<" "<<sR<<" "<<tL<<" "<<tR<<endl;
//cout<<contain(sL,sR,tL,tR)<<endl;
if(contain(sL,sR,tL,tR)==0){
trav(a,c){
int aL=a%1000;
int aR=a/1000;
if(contain(aL,aR,sL,sR)==-1){
return a;
}
}
}
if(contain(sL,sR,tL,tR)==-1){
trav(a,c){
int aL=a%1000;
int aR=a/1000;
//cout<<"A"<<a<<endl;
//cout<<contain(aL,aR,sL,sR)<<endl;
if(contain(aL,aR,tL,tR)==-1 && contain(aL,aR,sL,sR)==1){
//cout<<a<<endl;
return a;
}
}
}
trav(a,c){
int aL=a%1000;
int aR=a/1000;
if(contain(aL,aR,sL,sR)==-1){
return a;
}
}
}
