#include "stations.h"
#include <vector>
#include <bits/stdc++.h>
#define MAX 1000000000
using namespace std;
typedef vector<int> vi;
typedef pair<int,int> ii;
vector<int> labels;
vector<vi>G;
int vis[1010];
// task 3
/*void dfs(int u,int ns,int d){
vis[u]=1;
labels[u]=(1000*d+ns);
for(auto &v:G[u]){
if(!vis[v]){
dfs(v,ns,d+1);
}
}
}
void asignar(int u){
int ns=1;
labels[u]=0;
memset(vis,0,sizeof vis);
vis[u]=1;
for(auto &v:G[u]){
dfs(v,ns,0);
ns++;
}
}*/
std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
labels.assign(n,-1);
G.clear();
G.resize(n+1);
int t=u.size();
for(int i=0;i<t;i++){
int x=u[i],y=v[i];
G[x].push_back(y);
G[y].push_back(x);
}
// 10 points - task 4
labels[0]=1;
memset(vis,0,sizeof vis);
queue<ii> q;
q.push(ii(0,1));
while(!q.empty()){
int id=q.front().first;
int nl=q.front().second;
q.pop();
labels[id]=nl;
int lr=nl*8;
for(auto &v:G[id]){
if(labels[v]==-1){
q.push(ii(v,lr));
lr++;
}
}
}
// 13 points - task 3
/*int id=0;
for(int i=0;i<n;i++){
if(G[i].size()>2){
id=i;
break;
}
}
asignar(id);*/
// 8 points - taks 2
/*for(int i=0;i<n;i++) labels[i]=i;*/
// 5 points - task 1
/*int no=0,id=-1;
for(int i=0;i<n;i++){
if(G[i].size()==1){
id=i;
break;
}
}
queue<int> q;
q.push(id);
while(!q.empty()){
int x=q.front();
q.pop();
labels[x]=no;
no++;
for(auto &v:G[x]){
if(labels[v]==-1){
q.push(v);
}
}
}*/
return labels;
}
int find_next_station(int s, int t, std::vector<int> c) {
// 5 points - task 1
/* if(s>t)
return s-1;
return s+1;*/
// 8 points - task 2
/*queue<ii> q;
q.push(ii(s*2+1,0));
q.push(ii(s*2+2,1));
int res=-1;
while(!q.empty()){
int x=q.front().first;
int sw=q.front().second;
if(x==t){
res=sw;
break;
}
q.pop();
if(x*2+1<=t) q.push(ii(x*2+1,sw));
if(x*2+2<=t) q.push(ii(x*2+2,sw));
}
if(res==-1){
return c[0];
}
else{
if(s==0){
if(res==0) return c[0];
return c[1];
}
if(res==0) return c[1];
else return c[2];
}*/
// 16 points - task 3
/*if(s==0){
for(int i=0;i<c.size();i++){
if(c[i]%1000==t%1000){
return c[i];
}
}
}
else{
if(s%1000==t%1000){
if(s<t)
return s+1000;
return max(0,s-1000);
}
else{
return max(0,s-1000);
}
}*/
// 10 points - task 4
//cout<<s<<" "<<t<<endl;
int ls;
while(t!=0){
ls=t;
t/=8;
// cout<<t<<endl;
if(t<=s) break;
}
if(t==s) return ls;
else return s/8;
}
