Graph Reachability by Edge Type
Given an undirected graph with N nodes and M edges. Each edge is colored either 'red' or 'blue'. You are also given a starting node S. Determine the minimum number of steps to reach every other node from S, such that you can only traverse a red edge if you have previously traversed at least one blue edge, and you can always traverse a blue edge. If a node is unreachable, report -1 for it.
Input
The first line contains three integers N, M, and S (1-indexed) — the number of nodes, edges, and the starting node. The next M lines each contain three integers u, v, and c, representing an edge between u and v with color c (1 for blue, 2 for red).
Output
Print N integers, where the i-th integer is the minimum number of steps to reach node i from S. The distance to S itself is 0.
Constraints
1 <= N <= 200000, 1 <= M <= 200000, 1 <= S <= N. Node indices are 1-based. Edge colors are 1 (blue) or 2 (red).
Example 1
3 3 1 1 2 1 2 3 2 1 3 1
0 1 1
Start at node 1. Node 2 is reachable in 1 step (1->2, blue). Node 3 is reachable in 1 step (1->3, blue). If we went 1->2 (blue), then 2->3 (red) is possible, taking 2 steps.
Example 2
4 3 1 1 2 2 2 3 1 3 4 2
0 -1 -1 -1
Start at node 1. Node 2 is unreachable because only red edge exists initially. Node 3 is unreachable. Node 4 is unreachable. Only node 1 is reachable in 0 steps.
Hints
# Read the input from stdin and print the answer.
import sys
def main():
data = sys.stdin.read().split()
# your code here
main()
3 3 1 1 2 1 2 3 2 1 3 1
4 3 1 1 2 2 2 3 1 3 4 2