#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll ord[1005]; bool vis[1005]; ll timer=0;
vector<ll>adj[1005];
void dfs(ll s, bool pref){
vis[s]=1;
if(pref){
ord[s]=timer++;
}
for(auto& u: adj[s]){
if(!vis[u]){
dfs(u,!pref);
}
}
if(!pref)ord[s]=timer++;
}
vector<int> label(int n, int k, vector<int>u, vector<int>v){
for(int i=0;i<n;i++){
adj[i].clear(); vis[i]=0; timer=0;ord[i]=0;
}
for(int i=0;i<n-1;i++){
adj[u[i]].push_back(v[i]); adj[v[i]].push_back(u[i]);
}
dfs(0,1);
vector<int>rd(n);
for(int i=0;i<n;i++)rd[i]=ord[i]; return rd;
}
int find_next_station(int s, int t, vector<int>c){
if(c.size()==0){
return c[0];
}
if(s==0){
vector<pair<ll,ll> >alls;
for(int i=0;i<c.size();i++){
if(i==0)alls.push_back({1,c[i]});
else alls.push_back({c[i-1]+1,c[i]});
}
for(int i=0;i<alls.size();i++){
if(alls[i].first<=t&&t<=alls[i].second)return alls[i].second;
}
return -1;
}
else{
if(s<c[0]){
// prefix
ll lst=c[c.size()-1];
c.pop_back();
for(int i=0;i<c.size();i++){
if(i==0){
if(s<=t&&t<=c[i])return c[i];
}
else{
if(c[i-1]+1<=t&&t<=c[i])return c[i];
}
}
return lst;
}
else{
// suffix
ll lst=c[0]; reverse(c.begin(),c.end()); c.pop_back(); reverse(c.begin(),c.end());
for(int i=0;i<c.size();i++){
if(i==(int)c.size()-1){
if(c[i]<=t&&t<=s-1)return c[i];
}
else{
if(c[i]<=t&&t<=c[i+1]-1)return c[i];
}
}
return lst;
}
}
}
// int main(){
// ll n;
// cin>>n;
// vector<int>eu,ev;
// for(int i=1;i<n;i++){
// ll u,v;
// cin>>u>>v; adj[u].push_back(v); adj[v].push_back(u);
// eu.push_back(u); ev.push_back(v);
// }
// label(n,10000,eu,ev);
// for(int i=0;i<n;i++){
// cout<<ord[i]<<" ";
// }
// cout<<'\n';
// while(1){
// ll psu,psv; vector<int>neighbours;
// cin>>psu>>psv;
// ll ncount; cin>>ncount;
// for(int i=1;i<=ncount;i++){
// ll th; cin>>th; neighbours.push_back(th);
// }
// cout<<find_next_station(psu,psv,neighbours)<<"\n";
// }
// }
