#include "stations.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
typedef pair<int,int> ii;
std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
vector<int> labels;
labels.assign(n,-1);
// 8 points - taks 2
for(int i=0;i<n;i++) labels[i]=i;
// 5 points - task 1
/*vector<vi>G;
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);
}
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];
}
}
