#include<bits/stdc++.h>;

void BFS(int source, vector<int> &dist, unordered_map<int, list<int>> &red, unordered_map<int, list<int>> &blue) {

queue<array<int, 3>> q;

q.push({source, 0, 0}); // {node, color, distance}

q.push({source, 1, 0});

dist[source] = 0;

vector<vector<bool>> visited(dist.size(), vector<bool>(2, false)); // visited[node][color]

visited[source][0] = visited[source][1] = true;

while (!q.empty()) {

auto [node, color, distance] = q.front();

q.pop();

if (color != 0) { // not red

for (int neighbor : red[node]) {

if (!visited[neighbor][0]) {

visited[neighbor][0] = true;

dist[neighbor] = min(dist[neighbor], distance + 1);

q.push({neighbor, 0, distance + 1});

}

}

}

if (color != 1) { // not blue

for (int neighbor : blue[node]) {

if (!visited[neighbor][1]) {

visited[neighbor][1] = true;

dist[neighbor] = min(dist[neighbor], distance + 1);

q.push({neighbor, 1, distance + 1});

}

}

}

}

}

vector<int> shortestAlternateColoredPath(int n, vector<vector<int>>& redEdges, vector<vector<int>>& blueEdges)

{

unordered_map<int, list<int>> red, blue;

for (auto &edge : redEdges) {

red[edge[0]].push_back(edge[1]);

}

for (auto &edge : blueEdges) {

blue[edge[0]].push_back(edge[1]);

}

vector<int> dist(n, INT_MAX);

BFS(0, dist, red, blue);

for (int i = 0; i < n; ++i) {

if (dist[i] == INT_MAX) {

dist[i] = -1;

}

}

return dist;

}