#include "stations.h"
#include <bits/stdc++.h>
using namespace std;
#define ll int
#define F first
#define S second
#define MID ((l+r)/2)
#define sz(x) (ll)x.size()
#define pb push_back
#define dbg(x) cout<<#x<<": "<<x<<endl;
#define dbg2(x,y) cout<<#x<<": "<<x<<" "<<#y<<": "<<y<<endl;
#define dbg3(x,y,z) cout<<#x<<": "<<x<<" "<<#y<<": "<<y<<" "<<#z<<": "<<z<<endl;
typedef vector <ll> vi;
typedef pair<ll,ll> ii;
typedef vector <ii> vii;
void printVct(vi v){
for (ll i =0; i<sz(v); i++){
cout<<v[i]<<" ";
}
cout<<endl;
}
void printVctPair(vii v){
for (ll i =0; i<sz(v); i++){
cout<<"("<<v[i].F<<" "<<v[i].S<<"), ";
}
cout<<endl;
}
vector <vi> adj;
vi tin, tout, vis, labels;
ll dfsTimer = 0;
void dfs (ll u, bool parity){
vis[u] = 1;
tin[u] = dfsTimer;
dfsTimer++;
vis[u] = 1;
for (ll i=0;i<sz(adj[u]); i++){
if (!vis[adj[u][i]]){
dfs(adj[u][i], !parity);
}
}
tout[u] = dfsTimer;
dfsTimer++;
if (parity) labels[u] = tout[u];
else labels[u] = tin[u];
}
vi label(int n, int k, vi u, vi v){
adj.assign(n, vi());
for (ll i =0; i<n-1; i++){
adj[u[i]].pb(v[i]);
adj[v[i]].pb(u[i]);
}
tin.resize(n);
tout.resize(n);
vis.assign(n, 0);
labels.resize(n);
dfs(0, 0);
// cout<<"tin: ";
// printVct(tin);
// cout<<"tout: ";
// printVct(tout);
// cout<<"labels: ";
// printVct(labels);
vi labels_order(n);
for (ll i =0; i<n ;i++) labels_order[i] = i;
sort(labels_order.begin(), labels_order.end(), [&](ll a, ll b){ return (labels[a] < labels[b]);});
// cout<<"labels_order: ";
// printVct(labels_order);
vi labels_rank(n);
for (ll i = 0; i<n ;i++){
labels_rank[labels_order[i]] = i;
}
// cout<<"labels_rank: ";
// printVct(labels_rank);
return labels_rank;
}
// ll calls = 0;
int find_next_station(int s, int t, vi c) {
// calls++;
// cout<<endl<<endl<<"-------"<<calls<<"-------";
// dbg2(s,t);
// cout<<"c: "; printVct(c);
// cout<<endl;
//STEP 1: Find in or out
bool isin = (s < c[0]);
// dbg(isin);
//STEP 2: Find parent and remove
ll p;
sort(c.begin(), c.end());
if (isin){
p = c.back();
c.pop_back();
}
else{
p = c[0];
c.erase(c.begin());
}
// dbg(p);
//STEP 3: Find Range
vii ranges;
if (!isin){
for (ll i = 0; i<sz(c)-1; i++){
ranges.pb(ii(c[i], c[i+1]-1));
}
ranges.pb(ii(c.back(), s-1));
}
else{
ranges.pb(ii(s+1, c[0]));
for (ll i = 1; i<sz(c); i++){
ranges.pb(ii(c[i-1]+1, c[i]));
}
}
// cout<<"ranges: ";
// printVctPair(ranges);
//STEP 4: Solve
ll ans = p;
for (ll i =0; i<sz(ranges);i++){
if (t >= ranges[i].F && t <= ranges[i].S){
ans = c[i];
break;
}
}
// dbg(ans);
return ans;
}
