#include "stations.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
#define ii pair<int,int>
#define x first
#define y second
vector<int> labels;
vector<vector<int>> g;
int tme=0;
void dfs1(int i,int f=0,int t=0, int s=0){
int tin=tme++;
for(auto u:g[i]){
if(u!=f){
dfs1(u,i,(t+1)%2,(s+1)%3);
}
}
int tout=tme;
if(t==0){
labels[i]=6*tin+3*t+s;
}
else{
labels[i]=6*(tin+tout)+3*t+s;
}
}
std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
labels.assign(n,-1);
g.assign(n,vector<int>());
for(int i=0; i<n-1; i++){
g[u[i]].push_back(v[i]);
g[v[i]].push_back(u[i]);
}
dfs1(0);
return labels;
}
ii get(int x){
return ii(x/3%2,x%3);
}
int find_next_station(int s, int t, std::vector<int> c) {
ii r=get(s);
s/=6;
vector<pair<ii,int>> cld;
int f=-1;
if(r.x==0){
int prev=s;
for(auto i:c){
if(get(i).y!=(r.y+1)%3){
f=i;
continue;
}
int k=i/6;
cld.emplace_back(ii(prev+1,k-(prev+1)),i);
prev=k-(prev+1);
}
}
else{
for(auto i:c){
if(get(i).y!=(r.y+1)%3){
f=i;
continue;
}
if(!cld.empty())
cld.back().x.y=i/6-1;
cld.emplace_back(ii(i/6,-1),i);
}
if(!cld.empty()){
cld.back().x.y=s-(cld[0].x.x-1);
}
}
ii h=get(t);
t/=6;
for(auto i:cld){
if(h.x==0&&i.x.x<=t&&i.x.y>=t){
return i.y;
}
else if(h.x==1&&2*i.x.x<=t&&2*i.x.y>=t){
return i.y;
}
}
return f;
}
