Shortest Alternating Paths

Alice is given an undirected graph with n vertices labeled from 1 to n and m directed edges. Each edge is colored either red or blue. Starting from vertex 1, Alice wants to find the shortest distance to every other vertex with the constraint that the colors of the edges along the path strictly alternate. If a vertex is not reachable following the alternating color rule, output -1 for that vertex.

Formally, for a path v₁, v₂, ..., v_k, if the edge from v_i to v_i+1 is colored c_i, then for all valid indices i, c_i ≠ c_i+1 must hold. The distance is defined as the minimum number of edges needed to reach each vertex from vertex 1 obeying the alternating rule, with the distance to vertex 1 defined as 0.

Find a solution that reads input from the standard input (stdin) and writes output to the standard output (stdout).

Note: All formulas are presented in LaTeX format. For example, the alternating condition is \(c_i \neq c_{i+1}\).

inputFormat

The first line of input contains two integers \(n\) and \(m\) separated by a space, representing the number of vertices and edges respectively.

Each of the following \(m\) lines contains two integers and a string: \(u\), \(v\) and color. Here, \(u\) and \(v\) represent an edge from vertex \(u\) to vertex \(v\), and color is either "red" or "blue".

You may assume that \(1 \leq u, v \leq n\) and \(m \geq 0\).

outputFormat

Output a single line containing \(n\) integers separated by a space. The \(i\)-th integer denotes the shortest number of edges required to reach vertex \(i\) from vertex 1 following the alternating colors rule. If vertex \(i\) is not reachable, print -1 instead. Note that the distance for vertex 1 should always be 0.

4 5
1 2 red
1 3 blue
2 3 red
2 4 blue
3 4 red

0 1 1 2