#include <queue>
#include <algorithm>
using namespace ::std;
const int MAX_STATION = 40000;
const int MAX_LINE = 5;
const int INF = 1000000000;
int n;
bool isActive[MAX_STATION][MAX_LINE];
int prevStation[MAX_STATION][MAX_LINE];
int nextStation[MAX_STATION][MAX_LINE];
bool canTransfer[MAX_LINE][MAX_LINE];
void init(int N, int mLastStation1[5], int mLastStation2[5])
{
n = N;
for (int i = 0; i < n; i++)
for (int j = 0; j < MAX_LINE; j++)
isActive[i][j] = false;
for (int i = 0; i < MAX_LINE; i++)
for (int j = 0; j < MAX_LINE; j++)
canTransfer[i][j] = (i == j);
for (int i = 0; i < MAX_LINE; i++)
{
isActive[mLastStation1[i]][i] = true;
prevStation[mLastStation1[i]][i] = INF;
nextStation[mLastStation1[i]][i] = mLastStation2[i];
isActive[mLastStation2[i]][i] = true;
prevStation[mLastStation2[i]][i] = mLastStation1[i];
nextStation[mLastStation2[i]][i] = INF;
for (int j = 0; j < MAX_LINE; j++)
if (isActive[mLastStation1[i]][j] || isActive[mLastStation2[i]][j])
canTransfer[i][j] = canTransfer[j][i] = true;
}
}
void add(int mLine, int mPrevStation, int mStation)
{
int mNextStation = nextStation[mPrevStation][mLine];
isActive[mStation][mLine] = true;
nextStation[mPrevStation][mLine] = mStation;
prevStation[mStation][mLine] = mPrevStation;
nextStation[mStation][mLine] = mNextStation;
prevStation[mNextStation][mLine] = mStation;
for (int i = 0; i < MAX_LINE; i++)
if (isActive[mStation][i])
canTransfer[mLine][i] = canTransfer[i][mLine] = true;
}
int travelTime[MAX_STATION][MAX_LINE];
queue<pair<int, int>> travelTimeQ;
int minTravelTime(int mStartStation, int mEndStation)
{
travelTimeQ = {};
for (int i = 0; i < n; i++)
for (int j = 0; j < MAX_LINE; j++)
travelTime[i][j] = INF;
for (int i = 0; i < MAX_LINE; i++)
{
if (isActive[mStartStation][i])
{
travelTimeQ.push({mStartStation, i});
travelTime[mStartStation][i] = 0;
}
}
while (!travelTimeQ.empty())
{
int station = travelTimeQ.front().first;
int line = travelTimeQ.front().second;
int nowTravelTime = travelTime[station][line];
if(station == mEndStation)return nowTravelTime;
for (auto i : {prevStation[station][line], nextStation[station][line]})
{
if (i != INF && travelTime[i][line] == INF)
{
travelTimeQ.push({i, line});
travelTime[i][line] = nowTravelTime + 1;
}
}
for (int i = 0; i < MAX_LINE; i++)
{
if (isActive[station][i] && travelTime[station][i] == INF)
{
travelTimeQ.push({station, i});
travelTime[station][i] = nowTravelTime + 1;
}
}
travelTimeQ.pop();
}
return -1;
}
int transfer[MAX_LINE];
queue<int> transferQ;
int minTransfer(int mStartStation, int mEndStation)
{
transferQ = {};
for (int i = 0; i < MAX_LINE; i++)
transfer[i] = INF;
for (int i = 0; i < MAX_LINE; i++)
{
if (isActive[mStartStation][i])
{
transferQ.push(i);
transfer[i] = 0;
}
}
while (!transferQ.empty())
{
int line = transferQ.front();
int nowTransfer = transfer[line];
for(int i=0; i<5; i++)
{
if(isActive[mEndStation][i] && i == line)return nowTransfer;
}
for (int i = 0; i < MAX_LINE; i++)
{
if (canTransfer[line][i] && transfer[i] == INF)
{
transferQ.push(i);
transfer[i] = nowTransfer + 1;
}
}
transferQ.pop();
}
return -1;
}