#include "stations.h"
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int MX = 1042;
int in[MX];
int out[MX];
int dep[MX];
int dfsT = 0;
vector<int> adj[MX];
void dfs(int node, int par, int d) {
//cout << "cur " << node << '\n';
dep[node] = d;
in[node] = dfsT++;
for (auto& x: adj[node])
if (x != par)
dfs(x, node, d + 1);
out[node] = dfsT++;
}
vector<int> label(int n, int k, vector<int> u, vector<int> v) {
//cout << "called\n";
dfsT = 0;
vector<int> labels(n);
for (int i = 0; i < n; i++)
adj[i].clear();
for (int i = 0; i + 1 < n; i++) {
adj[u[i]].push_back(v[i]);
adj[v[i]].push_back(u[i]);
}
dfs(0, -1, 0);
for (int i = 0; i < n; i++)
labels[i] = ((dep[i] % 2) == 0) ? in[i] : out[i];
return labels;
}
int find_next_station(int s, int t, vector<int> c) {
c.push_back(s);
sort(c.begin(), c.end());
if (c[0] == s) {
// s is tin
// the rest is tout
int par = c.back(); // par has max tout
int curIn = c[0] + 1;
for (int i = 1; i + 1 < (int)c.size(); i++) {
int inTime = curIn;
int outTime = c[i];
if (inTime <= t && t <= outTime)
return c[i];
curIn = outTime + 1;
}
return par;
} else {
// s is tout
// the rest is tin
int par = c[0];
int curOut = c.back() - 1;
for (int i = (int)c.size() - 1; i > 0; i--) {
int inTime = c[i];
int outTime = curOut;
if (inTime <= t && t <= outTime)
return c[i];
curOut = inTime - 1;
}
return par;
}
}
