보행의 개수

그래프의 보행은 같은 정점과 같은 간선을 여러 번 지나도 되는 경로다. 보행의 길이는 그 보행에 들어 있는 간선의 개수다.

그래프가 주어졌을 때, 길이가 $L$인 보행의 개수가 $O(L^K)$가 되는 음이 아닌 정수 $K$ 중에서 가장 작은 값을 구하는 프로그램을 작성하시오.

보행의 개수가 $O(L^K)$라는 말은, 모든 양의 정수 $L$에 대해 길이가 $L$인 보행의 개수가 $C \times L^K$ 이하가 되는 상수 $C$가 존재한다는 뜻이다.

첫째 줄에 그래프의 정점 개수 $N$ $(2 \le N \le 50)$이 주어진다.

둘째 줄부터 $N$개의 줄에 그래프의 간선 정보가 인접 행렬로 주어진다. $i$번째 줄의 $j$번째 문자가 Y이면 정점 $i$에서 정점 $j$로 가는 간선이 있고, N이면 그런 간선이 없다. 자기 자신으로 가는 간선은 없다.

첫째 줄에 조건을 만족하는 가장 작은 음이 아닌 정수 $K$를 출력한다. 조건을 만족하는 $K$가 없으면 -1을 출력한다.

정점 세 개가 서로 양쪽 방향으로 모두 이어져 있으면 길이가 $L$인 보행의 개수는 $3 \times 2^L$이다. 이 값은 어떤 $K$로도 $O(L^K)$로 나타낼 수 없다.

사이클이 하나도 없는 그래프에서는 $L$이 $N$ 이상이면 보행의 개수가 0이다.

그래프가 서로 떨어진 사이클로만 이루어져 있으면 모든 $L$에 대해 보행의 개수가 $N$과 같다.