#include "stations.h"
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <ctime>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <limits>
#include <iomanip>
#include <unordered_set>
#include <unordered_map>
#include <random>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef ll itn;
#define ff first
#define ss second
ll n;
vector<int>g[1007];
int tin[1507], tout[1507];
int timer = 0;
vector<int>d;
void dfs(int v, int par = -1) {
tin[v] = timer++;
for (int i = 0; i < g[v].size(); i++) {
int to = g[v][i];
if (to != par) {
dfs(to, v);
}
}
tout[v] = timer++;
}
void raspr(int v, int par=-1, bool is_tin=true){
if(is_tin){
d.push_back(v);
}
for (int i = 0; i < g[v].size(); i++) {
int to = g[v][i];
if (to != par) {
raspr(to, v, !is_tin);
}
}
if(!is_tin){
d.push_back(v);
}
}
vector<int> label(int n, int k, vector<int> u, vector<int> v) {
vector<int> lbl(n);
for (int i = 0; i < n - 1; i++) {
g[v[i]].push_back(u[i]);
g[u[i]].push_back(v[i]);
}
raspr(0);
int tmr=0;
for(auto x:d){
lbl[x]=tmr++;
}
for (int i = 0; i < n; i++) {
tin[i] = 0;
tout[i] = 0;
timer = 0;
g[i].clear();
}
d.clear();
return lbl;
}
bool papa(int iv, int ov, int u) {
return (iv <= u && ov >= u);
}
bool is_in(int s, vector<int> c){
int mn=1e9,mx=0;
for(auto x:c){
mx=max(mx,x);
mn=min(mn,x);
}
return mn>=s;
}
int find_next_station(int s, int t, vector<int> c) {
if (c.size() == 1)return c[0];
sort(c.begin(),c.end());
if(s==0){
int is=s;
int os=c[c.size()-1];
for(int i=1;i<c.size();i++){
if(papa(c[i-1]+1,c[i],t)){
//cout<<c[i]<<" 1"<<endl;
return c[i];
}
}
//cout<<c[0]<<" 1"<<endl;
return c[0];
}
if(is_in(s,c)){
int is=s;
int par=c[c.size()-1];
int os=c[c.size()-2]-1;
if(!papa(is,os,t)){
return par;
}
for(int i=1;i<c.size()-1;i++){
if(papa(c[i-1]+1,c[i],t)){
//cout<<c[i]<<" 1"<<endl;
return c[i];
}
}
//cout<<c[0]<<" 1"<<endl;
return c[0];
}
else{
int os=s;
int par=c[0];
//cout<<"par: "<<par<<endl;
int is=c[1]+1;
if(!papa(is,os,t)){
return par;
}
for(int i=1;i<c.size()-1;i++){
//cout<<"ditarkel: "<<c[i]<<endl;
if(papa(c[i],c[i+1]-1,t)){
//cout<<c[i]<<" 2"<<endl;
return c[i];
}
}
//cout<<c[c.size()-1]<<" 2"<<endl;
return c[c.size()-1];
}
}
/*
1
8 1000000
0 1
0 2
1 3
1 4
3 5
3 6
5 7
5
7 2 5
2 3 0
6 5 3
7 4 5
6 4 3
1 8 1000 0 1 0 2 1 3 1 4 3 5 3 6 5 7 5 7 2 5 2 3 0 6 5 3 7 4 5 6 4 3
1 8 1000000
0 1
0 2
1 3
1 4
2 5
2 6
3 7
5
7 2 3
1 7 3
2 5 5
0 5 2
5 0 2
1
6 1000
0 1
0 2
0 3
1 4
1 5
5
0 1 1
0 2 2
0 3 3
0 4 1
0 5 1
*/
