마법 포털

왕국에는 마법 포털로 연결된 $n$개의 도시가 있다. 서로 다른 두 도시는 정확히 하나의 마법 포털로 연결되어 있으며, 이 포털을 타면 한 도시에서 다른 도시로 즉시 이동할 수 있다.

마법의 특성상 각 포털은 한 방향으로만 사용할 수 있다. 임의의 도시 A, B에 대해 포털로 A에서 B로 바로 갈 수 있는지, 또는 B에서 A로 바로 갈 수 있는지가 주어진다.

이 때문에 주민이 한 도시에서 다른 도시로 이동하려면 포털을 여러 번 거쳐야 할 때가 있다. 포털만으로는 서로 오갈 수 없는 도시 쌍도 있을 수 있다.

주민들은 포털만 이용해서 왕국의 다른 모든 도시에 갈 수 있는 도시를 완전한 도시라고 부른다. 처음 완전한 도시의 수를 $k$라고 하자.

왕은 도시 쌍을 하나 골라 그 사이 포털의 허용 방향을 반대로 바꾸려고 한다. 가장 좋은 선택을 하기 위해, 왕은 포털 하나의 방향만 바꿨을 때 왕국의 완전한 도시가 몇 개가 될 수 있는지 알고 싶어 한다.

왕은 부분 보고서 또는 전체 보고서를 요청할 수 있다. 보고서 내용은 매개변수 $L$에 따라 정해진다. 부분 보고서는 $L = k + 1$이고, 전체 보고서는 $L = 1$이다.

보고서에는 $m \ge L$인 정수 $m$마다, 다음 두 조건을 모두 만족하는 도시 쌍 (A, B)의 개수가 담긴다.

• 원래 포털로 A에서 B로 바로 갈 수 있다.
• 이 포털의 방향을 반대로 바꿔 B에서 A로 바로 갈 수 있게 하면 완전한 도시의 수가 $m$이 된다.

따라서 부분 보고서는 완전한 도시의 수를 실제로 늘리는 포털 하나의 변경만 다룬다. 전체 보고서는 포털 하나를 바꾸는 모든 경우를 다룬다.

주어진 허용 방향과 보고서 종류를 바탕으로 보고서를 만들어 아래 형식에 맞게 출력하는 프로그램을 작성하라.

첫 줄에는 두 정수 $n$($2 \le n \le 2000$)과 $p$가 주어진다. $n$은 도시의 수이고, $p$는 부분 보고서이면 0, 전체 보고서이면 1이다.

이어지는 $n$개의 줄에는 각각 $n$개의 문자가 주어진다. $i$번째 줄의 $j$번째 문자는 도시 $i$에서 도시 $j$로 바로 갈 수 있으면 +, 도시 $j$에서 도시 $i$로 바로 갈 수 있으면 –, $i = j$이면 .이다.

첫 줄에는 완전한 도시의 수 $k$를 출력한다.

$p = 0$이면 둘째 줄에 공백으로 구분한 $n - k$개의 0 이상 정수를 출력한다. $i$번째 수는 포털 방향을 바꿨을 때 완전한 도시의 수가 $k + i$가 되는 도시 쌍의 개수이다. $k = n$이면 둘째 줄은 없거나 비어 있어도 된다.

$p = 1$이면 둘째 줄에 공백으로 구분한 $n$개의 0 이상 정수를 출력한다. $i$번째 수는 포털 방향을 바꿨을 때 완전한 도시의 수가 $i$가 되는 도시 쌍의 개수이다.

예제에서 처음에 완전한 도시는 2번 도시뿐이다. 도시 쌍 (2, 3), (2, 4), (2, 5)의 포털 방향을 바꾸면 모든 도시가 완전한 도시가 된다. 그 밖의 포털 방향을 바꾸면 완전한 도시가 하나만 늘어난다.