#include "stations.h"
#include <algorithm>
#include <bits/stdc++.h>
#include <vector>
using namespace std;
vector<vector<int>> adj;
vector<int> tin, tout;
vector<int> depth;
int curTime;
void dfs(int u, int p) {
tin[u] = curTime++;
for (int v : adj[u])
if (v != p) {
depth[v] = depth[u] + 1;
dfs(v, u);
}
tout[u] = curTime++;
}
vector<int> label(int n, int k, vector<int> u, vector<int> v) {
curTime = 0;
tin.clear();
tout.clear();
depth.clear();
adj.clear();
tin.resize(n), tout.resize(n), adj.resize(n), depth.resize(n);
for (int i = 0; i < n - 1; ++i) {
adj[u[i]].push_back(v[i]);
adj[v[i]].push_back(u[i]);
}
dfs(0, 0);
vector<int> labels(n);
for (int i = 0; i < n; i++)
labels[i] = depth[i] % 2 ? tout[i] : tin[i];
vector<int> dis;
for (auto l : labels)
dis.push_back(l);
sort(dis.begin(), dis.end());
dis.resize(unique(dis.begin(), dis.end()) - dis.begin());
for (int &i : labels)
i = lower_bound(dis.begin(), dis.end(), i) - dis.begin();
// for (int x : labels)
// cerr << x << ' ';
// cerr << endl;
return labels;
}
int find_next_station(int s, int t, vector<int> c) {
if (!s) {
for (int i = 0; i < (int)c.size(); ++i)
if (t <= c[i])
return c[i];
}
if (c.size() == 1)
return c[0];
for (auto v : c)
if (v == t)
return v;
bool allGreater = true, allLess = true;
for (int i : c)
allGreater &= i > s, allLess &= i < s;
if (allGreater) { // s is tin, all others are tout
int p = c.back();
c.pop_back();
if (t < c[0] and t > s)
return c[0];
for (int i = 1; i < (int)c.size(); ++i)
if (t < c[i] and t > c[i - 1])
return c[i];
return p;
} else { // s is tout and all others are tin
int p = c.front();
c.erase(c.begin());
if (t > c.back() and t < s)
return c.back();
for (int i = 0; i + 1 < (int)c.size(); ++i)
if (t > c[i] and t < c[i + 1])
return c[i];
return p;
}
}
