#include "stations.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
int cnt=-1;
int dfs(vector<int>&labels,vector<bool>&visited,vector<vector<int>>&adj,int nodo,bool par){
cnt++;
visited[nodo]=true;
if(par){
labels[nodo]=cnt;
par=false;
}else{
par=true;
}
int maxi=0;
for(int j=0;j<adj[nodo].size();j++){
if(visited[adj[nodo][j]])continue;
maxi=max(maxi,dfs(labels,visited,adj,adj[nodo][j],par));
}
if(par){
cnt++;
labels[nodo]=cnt;
}
return labels[nodo];
}
std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
std::vector<int> labels(n);
cnt=0;
for (int i = 0; i < n; i++) {
labels[i] = i;
}
vector<int> indegree(n,0);
vector<vector<int>> adj(n,vector<int>(0,0));
for(int i=0;i<u.size();i++){
adj[u[i]].push_back(v[i]);
adj[v[i]].push_back(u[i]);
indegree[u[i]]++;
indegree[v[i]]++;
}
stack<int> st;
for(int i=0;i<n;i++){
if(indegree[i]==1){
st.push(i);
break;
}
}
vector<bool> visited(n,false);
dfs(labels,visited,adj,st.top(),1);
for(int i=0;i<labels.size();i++){
printf("%d ",labels[i]);
}
return labels;
}
int find_next_station(int s, int t, std::vector<int> c) {
int nans=INT_MAX,ans=0;
for(int i=0;i<c.size();i++){
if(c[i]>=t && c[i]-t<ans){
nans=min(ans,c[i]-t);
ans=i;
}
}
return c[ans];
}
