#include <bits/stdc++.h>
#include "stations.h"
#define all(x) x.begin(),x.end()
using namespace std;
vector <int> edges[1005];
int dfn;
void dfs(int x,int depth,int par,vector <int> &res)
{
if(depth & 1)
{
res[x]=dfn++;
for(auto u:edges[x])
{
if(u==par) continue;
dfs(u,depth+1,x,res);
}
}
else
{
for(auto u:edges[x])
{
if(u==par) continue;
dfs(u,depth+1,x,res);
}
res[x]=dfn++;
}
}
vector <int> label(int n,int k,vector <int> _ea,vector <int> _eb)
{
dfn=0;
assert((int)_ea.size()==n-1);
vector <int> res;
res.resize(n);
for(int i=0;i<n;i++)
{
edges[i].clear();
}
for(int i=0;i<n-1;i++)
{
edges[_ea[i]].push_back(_eb[i]);
edges[_eb[i]].push_back(_ea[i]);
}
dfs(0,0,-1,res);
return res;
}
int find_next_station(int s,int t,vector <int> c)
{
// return 0;
if(s>c[0]) // ºó¸ù
{
sort(all(c));
int par=*c.begin();
c.erase(c.begin());
if(c.empty()) return par;
if(t<c.front() || t>=s) return par;
reverse(all(c));
for(auto x:c)
{
if(t>=x) return x;
}
}
else // Ïȸù
{
sort(all(c));
int par=*(--c.end());
c.erase(--c.end());
if(c.empty()) return par;
if(t>c.back() || t<=s) return par;
for(auto x:c)
{
if(t<=x) return x;
}
}
// assert(false);
return -1;
}
