#include "stations.h"
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
const int maxn = 2e3 + 10;
vector < int > g[maxn];
int tmr = -1;
int used[maxn];
int tin[maxn], tout[maxn], depth[maxn];
void dfs(int beg, int from, int h)
{
used[beg] = 1;
depth[beg] = h;
tmr ++;
tin[beg] = tmr;
for (auto nb: g[beg])
{
if(used[nb])continue;
dfs(nb, beg, h+1);
}
tmr ++;
tout[beg] = tmr;
}
std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v)
{
memset(used, 0, sizeof(used));
for (int i = 0; i < n; ++ i)
g[i].clear();
for (int i = 0; i < n; ++ i)
tin[i] = tout[i] = 0;
tmr = -1;
for (int i = 0; i < n-1; ++ i)
{
g[u[i]].pb(v[i]);
g[v[i]].pb(u[i]);
}
dfs(0, -1, 0);
std::vector<int> labels(n);
vector < pair < int, int > > mp;
for (int i = 0; i < n; i++)
{
if(depth[i] & 1)labels[i] = tout[i];
else labels[i] = tin[i];
mp.pb(make_pair(labels[i], i));
}
sort(mp.begin(), mp.end());
int nomer = 0;
for (auto &[val, index]: mp)
{
labels[index] = nomer;
nomer ++;
}
return labels;
}
int find_next_station(int s, int t, std::vector<int> c)
{
int case1 = 1;
for (auto x: c)
{
if(s > x)
{
case1 = 0;
break;
}
}
if(case1)
{
/// par - tout
/// s - tin
/// kid - tout
int par = -1;
if(s != 0)
{
par = c.back();
c.pop_back();
}
int ins = s, outs = s+1;
vector < int > in, out;
int kids = c.size();
for (auto x: c)
out.pb(x);
if(kids)
{
in.pb(s + 1);
for (int i = 1; i < kids; ++ i)
{
in.pb(out[i-1] + 1);
}
outs = out.back() + 1;
}
for (int i = 0; i < kids; ++ i)
{
if(in[i] <= t && t <= out[i])
return out[i];
}
return par;
}
else
{
/// tin
/// tout
/// tin
int par = c[0];
int ins = s-1, outs = s;
vector < int > in, out;
for (int i = 1; i < c.size(); ++ i)
in.pb(c[i]);
int kids = in.size();
if(kids)
{
out.pb(s - 1);
for (int i = kids-2; i >= 0; -- i)
{
out.pb(in[i+1] - 1);
}
reverse(out.begin(), out.end());
}
for (int i = 0; i < kids; ++ i)
{
if(in[i] <= t && t <= out[i])
return in[i];
}
return par;
}
}
/**
2
7 10000000
0 1
0 2
0 6
2 3
2 4
3 5
4
6 3 0
4 1 2
3 4 2
4 3 2
7 10000000
0 1
0 2
0 6
2 3
2 4
3 5
4
6 3 0
1 3 0
3 4 2
4 3 2
*/
