#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];
void dfs(int beg, int from)
{
used[beg] = 1;
tmr ++;
tin[beg] = tmr;
for (auto nb: g[beg])
{
if(used[nb])continue;
dfs(nb, beg);
}
//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);
std::vector<int> labels(n);
for (int i = 0; i < n; i++)
{
labels[i] = tin[i] * 1000 + tout[i];
//assert(labels[i] > 0);
}
return labels;
}
int find_next_station(int s, int t, std::vector<int> c)
{
int tins, touts;
int tint, toutt;
touts = s%1000;
tins = s/1000;
toutt = t%1000;
tint = t/1000;
int paris = -1;
for (auto par: c)
{
int outpar = par%1000;
int inpar = par/1000;
if(inpar <= tins && touts <= outpar)
{
paris = par;
break;
}
}
if(paris != -1)
{
int outpar = paris%1000;
int inpar = paris/1000;
vector < int > newc;
for (auto x: c)
{
if(x == paris)continue;
newc.pb(x);
}
c = newc;
}
if(tins <= tint && toutt <= touts)
{
for (auto x: c)
{
int out = x%1000;
int in = x/1000;
if(in <= tint && toutt <= out)
{
return x;
}
}
}
return paris;
}
/**
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
*/
