#include "stations.h"
// author : sentheta aka vanwij
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<cassert>
#include<random>
#include<chrono>
#include<cmath>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<stack>
#include<map>
#include<set>
using namespace std;
#define Int long long
#define V vector
#define pii pair<int,int>
#define ff first
#define ss second
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
#define pow2(x) (1LL<<(x))
#define msb(x) (63-__builtin_clzll(x))
#define bitcnt(x) (__builtin_popcountll(x))
#define nl '\n'
#define _ << ' ' <<
#define all(x) (x).begin(), (x).end()
#define rep(i,a,b) for(int i = (int)(a); i < (int)(b); i++)
#define dbg(x) if(1) cout << "?" << #x << " : " << (x) << endl << flush;
const int N = 1005;
V<int> adj[N];
int d[N];
int in[N], out[N];
int t = 0;
void dfs(int x=0,int par=-1){
in[x] = t++;
for(int y : adj[x]) if(y!=par){
d[y] = d[x]+1;
dfs(y, x);
}
out[x] = t++;
}
V<int> label(int n,int k,V<int> u,V<int> v){
rep(i,0,n){
adj[i].clear();
}
rep(i,0,n-1){
adj[u[i]].push_back(v[i]);
adj[v[i]].push_back(u[i]);
}
t = 0;
dfs();
map<int,int> zip;
rep(i,0,n){
if(d[i]%2==0) zip[in[i]];
else zip[out[i]];
}
t = 0;
for(auto&[p,q] : zip) q = t++;
V<int> ans;
rep(i,0,n){
if(d[i]%2==0) ans.push_back(zip[in[i]]);
else ans.push_back(zip[out[i]]);
}
return ans;
}
int find_next_station(int s,int t,V<int> c){
// s is in[x]
if(s < c[0]){
int par = s==0 ? -1 : c.back();
int l = s+1;
for(int r : c) if(r!=par){
if(l<=t && t<=r) return r;
l = r+1;
}
return par;
}
// s is out[x]
else{
int par = c[0];
c.push_back(s);
rep(i,0,c.size()-1){
if(c[i]<=t && t<=c[i+1]-1) return c[i];
}
return par;
}
}
