Constrained Color‐Switching Hamiltonian Path

You are given a complete undirected graph with N vertices. Every edge has a weight of 1 and is colored either red or blue. For each vertex s (numbered from 1 to N) you are required to construct a path starting at s that visits every vertex at least once, such that the total weight (i.e. the number of edges used) is minimized.

The twist is that whenever you travel from one edge to the next, if the colors of these two consecutive edges are different, you must spend a ticket. You are allowed to spend at most one ticket during your entire path. In other words, the sequence of edges used in your path must be almost monochromatic – it can consist of a single contiguous block of one color, or it can be split into two contiguous segments: the first segment of one color and the second segment of the other color. Note that you are allowed to revisit vertices.

Your task is to compute, for every starting vertex, the minimum number of edges needed to complete such a path. It is guaranteed that the graph is complete so there is an edge between every pair of distinct vertices.

Input Format: The first line contains an integer N (the number of vertices). The following N lines each contain a string of length N. In the i-th line, the j-th character describes the color of the edge between vertex i and vertex j: it is either 'R' (red) or 'B' (blue) for i ≠ j, and the diagonal character (when i = j) will be '-' (a placeholder that should be ignored).

Output Format: Output a single line containing N space‐separated integers. The i-th integer should be the minimum number of edges required for a valid path starting from vertex i that visits all vertices at least once under the given conditions. It is guaranteed that a valid path exists for every starting vertex.

Note: All formulas in this problem statement (for example, the summation of weights etc.) are provided in LaTeX: the edge weight is always \(1\), and the number of vertices is \(N\).

inputFormat

The input begins with a line containing an integer \(N\) (the number of vertices). The next \(N\) lines each contain a string of length \(N\). For the i-th line, the j-th character is:

• 'R' if the edge between vertices \(i\) and \(j\) is red (\(i \neq j\));
• 'B' if the edge is blue (\(i \neq j\));
• '-' if \(i = j\), which should be ignored.

outputFormat

Output a single line containing \(N\) space-separated integers. The \(i\)-th integer represents the minimum number of edges required for a valid path starting from vertex \(i\) that visits every vertex at least once under the switching rule.

sample

2
-R
R-

1 1