도로

0번부터 N-1번까지 번호가 붙은 N개의 도시가 있고, 일부 도시 쌍 사이에는 양방향 도로가 있다.

각 도로에는 우선순위가 있다. A < B, C < D인 두 도로 (A, B)와 (C, D)를 생각하자. 튜플 (A, B)가 (C, D)보다 사전순으로 작으면, 도로 (A, B)의 우선순위가 더 높다. 사전순 비교에서는 두 튜플에서 처음으로 값이 다른 위치를 보고, 그 값이 더 작은 튜플을 더 작다고 한다.

도로 집합은 포함된 도로들을 우선순위가 높은 순서대로 정렬해 나타낸다. 도로 집합 사이의 우선순위도 이렇게 정렬된 도로 튜플들의 사전순으로 비교한다. 어떤 도로 집합에 포함된 도로만 사용해서 임의의 도시에서 다른 임의의 도시로 이동할 수 있으면, 그 도로 집합은 연결되어 있다고 한다.

정확히 M개의 도로를 포함하는 연결된 도로 집합 중 우선순위가 가장 높은 것을 구하라.

첫째 줄에 도시의 개수 N과 선택해야 하는 도로의 개수 M이 주어진다. N은 50 이하의 자연수이고, M은 N-1 <= M <= 1,000을 만족하는 정수이다.

둘째 줄부터 N개의 줄에는 인접 행렬이 주어진다. 이 중 i번째 줄의 j번째 문자가 Y이면 도시 i와 도시 j를 잇는 도로가 존재하고, N이면 존재하지 않는다. 행렬은 대칭이며, 어떤 도시도 자기 자신과 연결되어 있지 않다.

정답이 없으면 -1을 출력한다.

정답이 있으면 선택된 도로 중 0번 도시를 끝점으로 갖는 도로의 개수, 1번 도시를 끝점으로 갖는 도로의 개수, ..., N-1번 도시를 끝점으로 갖는 도로의 개수를 차례로 출력한다.