시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 77 24 19 27.536%

문제

0부터 N-1까지번호 매겨져 있는 N개의 도시가 있다. 어떤 도시들은 도로로 연결되어 있다. 도로에는 중요도가 있는데, A와 B가(A<B) 도로로 연결되어 있고, C와 D가(C<D) 도로로 연결되어 있을 때, 그리고, A<C 이거나 (A=C이고, B<D)일 때, A와 B를 연결한 도로가 C와 D를 연결한 도로보다 중요하다.

도로의 집합은 하나 또는 그 이상의 도로가 높은 우선 순위에서 낮은 우선 순위로 정렬되어 있는 것이다. 집합도 집합들 사이에 우선 순위가 있는데, 집합 S1과 집합 S2가 있을 때, S1[i]가 S2[i]보다 높은 우선 순위를 가질 때, S1이 S2보다 우선 순위가 높다. i는 두 집합의 원소가 서로 다른 첫 번째 원소이다. 도로의 집합이 연결되어 있다는 말은, 그 집합에 있는 도로만으로, 모든 도시가 서로 다른 도시로 경로가 있을 때이다.

김지민이 할 일은 M개의 도로를 가진 도로의 집합 중 연결되어 있으면서, 가장 우선 순위가 높은 것을 찾는 것이다. 그러한 프로그램을 작성하시오.

입력

첫째 줄에 도시의 개수 N과 M이 주어진다. N은 50보다 작거나 같은 자연수이고, M은 N-1보다 크거나 같고, 1,000보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 각 도시가 어떻게 연결되어 있으면 Y, 아니면 N이 주어진다. 인접행렬이 주어진다. (예제 참고) i와 j가 연결되어 있으면, j와 i도 연결된 것이고, i와 i는 연결되어 있지 않다.

출력

만약 정답이 없을 때는 -1을 출력한다. 그렇지 않으면, 문제의 정답에 해당하는 집합 중에 0이 끝점인 것의 개수, 1이 끝점인 것의 개수, ..., N-1이 끝점인 것의 개수를 출력한다.

예제 입력

3 2
NYY
YNY
YYN

예제 출력

2 1 1

힌트

출처