#include <bits/stdc++.h>
#include "stations.h"
#define pii pair<int,int>
#define in first
#define out second
#define mp make_pair
using namespace std;
vector<int> label(int n ,int k , vector<int> u , vector<int> v){
vector<int> ans(n) ;
vector<int> adj[n] ;
for(int i=0;i<n-1;i++) {
adj[u[i]].push_back(v[i]) ;
adj[v[i]].push_back(u[i]) ;
}
int tim = 0 ;
vector<int> inn(n) , outt(n) ;
function<void(int,int)> dfs = [&](int a, int p){
inn[a]=tim++;
for(int x :adj[a]){
if(x!=p){
dfs(x,a) ;
}
}
outt[a]=tim++ ;
};
dfs(0,0) ;
for(int i=0;i<n;i++)
ans[i]=inn[i]+((outt[i])<<11);
return ans ;
}
pii get(int x){
return mp(x%(1<<11),(x>>11)) ;
}
bool ancestor(pii s, pii b){
return (s.in<=b.in&&b.out<=s.out);
}
int find_next_station(int s ,int t, vector<int> ne){
pii ss = get(s) , tt = get(t) ;
if(ancestor(ss,tt)^1){
for(int x : ne){
if(ancestor(get(x),ss)){
return x ;
}
}
}
for(int x : ne){
if(ancestor(get(x),ss)^1 && ancestor(get(x),tt)){
return x ;
}
}
if(s==t) return s ;
return 1 ;
}
/*int main(){
vector<int> u= {0,1,2} , v = {1,2,3} ;
vector<int> res = label(4,1000000,u,v) ;
for(int x : res) cout << x <<" " ;
cout << endl ;
for(int i=0;i<4;i++){
for(int j=0;j<4;j++){
if(i!=j){
cout << i << " "<< j << ": " << find_next_station(i,j,adj[i]) << endl ;
}
}
}
return 0 ;
}*/
