#include "stations.h"
#include<bits/stdc++.h>
#define ss second
#define all(s) s.begin(),s.end()
#define sz(s) ll(s.size())
#define pb push_back
typedef long long ll;
const ll MAX=1e6;
using namespace std;
ll marc=1, q;
vector<ll> gfo[MAX];
ll m[MAX], tam[MAX];
bool vst[MAX];
void dfs(int u, int f){
m[u]=marc;
for(auto v:gfo[u]){
if(v!=f){
marc+=q;
dfs(v,u);
}
}
}
vector<int> label(int n, int k, vector<int> u, vector<int> v){
vector<int> labels(n);
for(int i=0; i<sz(u); i++){
gfo[u[i]].pb(v[i]);
gfo[v[i]].pb(u[i]);
}
for(int i=0; i<n; i++){
if(sz(gfo[i])>2){
q=sz(gfo[i]);
m[i]=0;
for(int j=0; j<sz(gfo[i]); j++){
int v=gfo[i][j];
marc=j+1;
dfs(v, i);
}
break;
}
}
for(int i=0; i<n; i++){
labels[i]=m[i];
m[i]=0;
gfo[i].clear();
}
return labels;
}
int find_next_station(int s, int t, vector<int> c){
sort(all(c));
// cout<<s<<' '<<t<<' '<<' ';
// for(auto x:c){
// cout<<x<<' ';
// }
// cout<<'\n';
ll md=abs(c[sz(c)-1]-s);
if(s==0 || t==0){
if(s==0){
for(auto x:c){
if(x%md==t%md){
return x;
}
}
}
return c[0];
}
if(s%md != t%md){
return c[0];
}
if(t>s){
return c[sz(c)-1];
}
return c[0];
}
