Problem Description

In a kingdom, there are $n$ cities connected by magic portals.

For every pair of different cities, there is exactly one magic portal, which allows instant travel from one city to the other.

Due to the special nature of the magic portals, each portal can only be used in one direction. For each pair of cities $A$ and $B$, it is known whether the portal can be used from $A$ to $B$ or from $B$ to $A$.

Because of this, residents sometimes need to use multiple portals to travel from one city to another. Also, it is possible that some pairs of cities are not reachable from each other using any sequence of portals.

Residents call a city a “perfect city” if it is possible to reach all other cities in the kingdom from that city using only magic portals. Suppose initially there are $k$ perfect cities in the kingdom.

Recently, the king decided to choose one pair of cities and reverse the direction of the portal connecting them. To choose the best plan, the king wants to know how the number of perfect cities in the kingdom may change after modifying one portal.

The report should include, for each integer $m$ with $m \geq L$, the number of ordered city pairs $(A, B)$ that satisfy:

• In the original portal system, it is possible to travel directly from city $A$ to city $B$.
• If this portal direction is reversed so that it is possible to travel directly from city $B$ to city $A$, then the number of perfect cities in the kingdom becomes $m$.

Therefore, the partial report contains only those changes that strictly increase the number of perfect cities. The full report contains all outcomes obtained by reversing the direction of exactly one portal.

To obtain this information, the king plans to request a report from the Ministry of Transportation. The king can request a partial report or a full report. The content of the report depends on the parameter $L$: for the partial report, $L = k + 1$, and for the full report, $L = 1$.

Task: Write a program that generates the required report based on the given portal directions.

Input Format

The first line of the input file contains two integers: $n$ — the number of cities in the kingdom ($2 \leq n \leq 2000$), and $p$, where $p = 0$ means you need to output the partial report, and $p = 1$ means you need to output the full report.

The next $n$ lines contain $n$ characters each. The $j$-th character in the $i$-th line describes the portal between city $i$ and city $j$:

• “+” means you can travel from city $i$ to city $j$.
• “-” means you can travel from city $j$ to city $i$.
• “.” means there is no portal (i.e. $i = j$).

Output Format

The first line of the output file should contain one integer $k$ — the number of perfect cities in the kingdom.

If a partial report is required ($p = 0$), then the second line should contain $n - k$ non-negative integers separated by spaces. The $i$-th number represents how many portal reversals on a city pair $(A, B)$ make the number of perfect cities become $k + i$. If $k = n$, the second line may be empty.

If a full report is required ($p = 1$), then the second line should contain $n$ non-negative integers separated by spaces. The $i$-th number represents how many portal reversals on a city pair $(A, B)$ make the number of perfect cities become $i$.

5 0
.-+++
+.+++
--.+-
---.+
--+-.

1
0 0 0 3

5 1
.-+++
+.+++
--.+-
---.+
--+-.

1
7 0 0 0 3

Hint

Example Explanation

In this example, initially only city $2$ is perfect. By reversing the portal directions connecting city pair $(2, 3)$, $(2, 4)$, and $(2, 5)$, all cities become perfect. Reversing any other portal makes only one city perfect.

Grading System and Subtasks

Subtask 1 (20 points)

• $2 \leq n \leq 50$, $p = 0$.

Subtask 2 (30 points)

• $2 \leq n \leq 300$, $p = 0$.

Subtask 3 (20 points)

• $2 \leq n \leq 2000$, $p = 0$.

Subtask 4 (30 points)

• $2 \leq n \leq 2000$, $p = 1$.

Translation source: GPT 5.2.

Translated by ChatGPT 5