#include "stations.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> label(int n, int k, vector<int> u, vector<int> v) {
vector<vector<int>> adj(n+1); // +1 shift
for(int i=0;i<n-1;i++){
adj[u[i]+1].push_back(v[i]+1);
adj[v[i]+1].push_back(u[i]+1);
}
vector<int> lbl(n);
for(int i=1;i<=n;i++){
int ans=0;
for(int j=0;j<adj[i].size();j++){
vector<int> visited(n+1, 0);
visited[i]=1;
visited[adj[i][j]]=1;
queue<int> q;
int tttt = adj[i][j];
for(int ij=0;ij<adj[tttt].size();ij++) q.push(adj[tttt][ij]);
while(!q.empty()){
int x = q.front(); q.pop();
if(!visited[x]){
visited[x]=1;
ans = ans*10 + x;
for(int ij=0;ij<adj[x].size();ij++) q.push(adj[x][ij]);
}
}
ans = ans*10 + adj[i][j];
}
ans=ans*10+i;
lbl[i-1] = ans;
}
/*
for (int i=0; i<n; i++){
cout<<lbl[i]<<"\n";
}
*/
return lbl;
}
int find_next_station(int s, int t, vector <int> cp){
int target=t%10-1;
vector <int> c;
while (s>0){
c.push_back(s%10-1);
s=s/10;
}
reverse(c.begin(),c.end());
//cout<<c[0]<<' '<<c[1]<<' '<<c[2]<<"\n";
for (int i=0; i<c.size(); i++){
if (c[i]==target){
for (int j=i; j<c.size(); j++){
for (int z=0; z<cp.size(); z++){
//cout<<"tst "<<cp[z]<<" "<<c[j]<<"\n";
if (cp[z]%10-1==c[j]){return cp[z];}
}
}
}
}
return cp[0];
}
