시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 512 MB95555.556%

문제

그래프의 보행이란 같은 정점, 간선을 여러 번 방문할 수 있는 경로를 말한다. 보행의 길이란 보행에 포함되어 있는 간선의 개수이다.

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

경우의 수가 O(LK)라는 것은 임의의 양의 정수 L에 대해서, 길이가 L인 보행의 개수가 C×LK 이하를 만족하는 상수 C가 존재한다는 뜻이다.

입력

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

둘째 줄부터 N개의 줄에는 그래프 간선의 정보가 인접 행렬 형식으로 주어진다. Y인 경우에는 간선이 있는 것이고, N인 경우에는 간선이 없는 것이다. 같은 정점을 연결하는 간선은 없다.

출력

첫째 줄에 문제의 조건을 만족하는 가장 작은 음이 아닌 정수 K를 출력한다. 조건을 만족하는 K가 없는 경우에는 -1을 출력한다.

예제 입력 1

3
NYY
YNY
YYN

예제 출력 1

-1

예제 입력 2

5
NYNNN
NNYNN
NNNYN
NNNNY
NNNNN

예제 출력 2

0

예제 입력 3

5
NYNNN
YNNNN
NNNYN
NNNNY
NNYNN

예제 출력 3

0

예제 입력 4

20
NYYYNYYYNNYYYYYYNYNN
NNNNYNYYNNYYYNYYNYYN
NYNNYYYNNNYYYYNYNYNN
NYYNNYYYYNNNYYNNYNYY
NYNYNNNNNNYYYYYNYYYN
YNNNNNNYNNYNNYYYYYYY
NNYYNNNNNYNYNYNNYNYY
NNYNYYNNNNYNYNYYYYNN
NYYNYYNNNYNNYYYNYNYN
YYNNYNNYYNYNNNNNYNNN
YYNYYNNYYYNYYNYNYYYY
YYNNYYNYNYNNNNYNNNNY
NNYYNYYYNNNNNYYYYYNY
YNNNYNNNNYNNNNNYNNNY
YYYYNYYNNYNNNNNYNNNN
NYYYYNYNYYNNYNNNYNNY
YYYYYNNNYYYYNYYYNNYN
NNYNNYNYNYNNNNNNYNYN
YYNYYNNNNNYNNYNYNNNY
YYYYNYNYYNNYNYNYNNNN

예제 출력 4

-1

예제 입력 5

50
NYNYYYNYYYNYYNYYNYYNYYNYNNYYYYNNNYYNNNYNYYNYNNNYNY
NNNNNNNNNNNNNNNNYNNNYNNNNNYNYNYNNNNNNYNNNNNNNNNNNN
NYNYYYYNYNYYNNYYYYYYYYYYNYYYNYYYYYYNNYYYYYYYNNYYYY
NYNNYYNNNNNNNNNNNYNNNYNYNNYNYNYYNYYNNYYYNNNNNNNYYY
NNNNNNNNNNNNYNNYYNNNYNNNNYNNYNNYNNYNNYNYNNNNNNNYYN
NNNNNNNNNNNNNNNNYNNNYNNNNNNNNNYNNNNNNYNNNNNNNNNNNN
YYNYNNNYNYYYYNYYYYYYYYYYNYYYYYYYNYYNNYNYYYYYNNYNYY
NYNYYNNNYYNNYNNYYYNNYYNYNYYNYYYNNNYNNYYYNNNNNNNYYY
NYNYYYNYNYNNNNNYYYNNNNNNNYYNYYYYNYYNNYYYNNNNNNNYYY
NYNNNYNNNNNNNNNYYNNNYNNNNNYNYNYNNYYNNYNYNNNYNNNNYN
NYNYYYNNYYNYYNYNYYNYYYNYNYYNYYYYNYNNNNYYYYNYNNNYNY
NYNNYYNNNYNNYNNYYYNNYYNNNYYNYYNNNYYNNNNYNNNYNNNYYY
NNNNNNNNNNNNNNNYYNNNYNNNNNNNYNNYNYNNNYYNNNNNNNNYNN
YYYYNYYYYYYYYNYYYYNYYYYYYYYYYYNYYNYYYNYYYYYNNYYNYN
NYNYYNNYYYNYYNNYYYNYNYNYNYYNYYYYNYYNNYYYYYNYNNNNNY
NYNNNNNNNNNNNNNNYNNNYNNNNNYNYNYYNYNNNNNNNNNNNNNNNN
NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNYNNNNNNNNNNNNNNNNNNN
NYNNNYNNNNNNNNNYYNNNNNNNNNNNYNYYNYYNNYNNNNNNNNNYYN
NYNYYYNNYYNYNNYYYYNYYYNYNYYYYNNYNNYNNYNYYYYNNNYYYY
NNNYYYNNNYNYYNNYYYNNYYNNNYYNYYYYNYYNNNYYNYNYNNNYYY
NNNNNNNNNNNNNNNNNNNNNNNNNNYNNNNNNNNNNNNNNNNNNNNNNN
NYNNNYNNNNNNNNNYNNNNNNNNNYYNYYYYNYYNNYNNNNNNNNNYYN
YYNYYYNNYYNYYNYNYYNYNYNYNYYYYYYYNYNNNYYYYYNYNNYYYY
NYNYYYNNNNNNYNNNYYNNYYNNNYYNYYYYNYYNNYYYNNNNNNNYNY
YNNNYYYYYYYYYNYYYYYYYYYNNYYNYNYNYNNYYYYYYYNYNNYYYY
NYNNNYNNNNNNNNNYYNNNYNNNNNYNYNYYNYYNNNNYNNNNNNNYNN
NNNNNNNNNNNNNNNNNNNNNNNNNNNNYNNNNNNNNNNNNNNNNNNNNN
NYNYYYNYYYNYNNNNYYNYYNNYNYYNYYYYNYYNNNNNYYNYNNYYNN
NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNYNNNNNNNNNNNN
NYNNNYNNNNNNNNNYYNNNYNNNNNNNNNYYNYYNNNNYNNNNNNNYYY
NNNNNNNNNNNNNNNNYNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN
NNNNNNNNNNNNNNNNYNNNYNNNNNYNNNYNNNNNNNNNNNNNNNNNNN
NYNYYNNYYYNNNNNYYYNYYYNNNYYYYYYYNYYNNYYYYNNYNNNNYY
NNNNNNNNNNNNNNNYYNNNYNNNNNYNYNYYNNNNNYNNNNNNNNNNNN
NYNNNNNNNNNNNNNNYNNNYNNNNNYNNNYYNNNNNNNNNNNNNNNYNN
NYNYYYYYNYYYYNYYYYYYNYYYNNNYYYYYNYYNYNYYYYYYNYYYNY
YYNYYYNYYYNNNNNYNYYYYNYNNNYYYYYYNYYNNYYNYNNYNNYNNY
NNNNNNNNNNNNNNNNNNNNYNNNNNNNNNNNNNNNNNNNNNNNNNNNNN
NYNNNYNNNNNNNNNYYNNNNYNNNNYNYNNYNNNNNYNYNNNNNNNYNN
NYNNNYNNNNNNNNNYYNNNNNNNNYYNYNYNNYYNNNNNNNNNNNNYNN
NYNYYYNYYYNYNNNNNYNNYYNYNNYNNYYYNYYNNYYYNNNNNNNYYY
NYNYYNNNNYNYYNNYYYNYYYNNNYYNYYYNNYYNNYYYNNNYNNNNYY
NYNYNYNYYYNYYNYYNYNYNYYYNNYYYYYYNNNNNYYYNYNYNNYNYY
NYNNNYNNNYNNNNNYYYNNYNNNNNYNYNNNNYYNNYNYNNNNNNNYYN
YYYNNYNYYYNYNNYYYYYNYYNYNYYYYYNYYNYNYYYYYNNYNNYNYN
YYNNYYYYYYYNYNYYNYYYYYYYYYYNYYYNYYYNNYYYYNYYNNYYYY
NYNNYYNYYYNNYNNYYYNYNYNYNYYNNYYNNYNNNYYYNYNYNNNNYY
NNNNNNNNNNNNNNNNYNNNNNNNNNNNNNYNNNNNNNNNNNNNNNNNNN
NNNNNNNNNNNNNNNNNNNNYNNNNNYNYNYNNNNNNYNNNNNNNNNYNN
NYNNYYNNNNNNNNNYYNNNNNNNNYYNYNNYNYYNNYNYNNNNNNNYNN

예제 출력 5

7

힌트

예제 1의 경우에 길이가 L인 보행의 개수 3*2^L이다. 이 값은 O(LK)로 나타낼 수 없다.

예제 2의 경우에 L이 크면, 보행의 개수가 0이 된다.

예제 3의 모든 L에 대해서, 보행의 개수가 5이다.

출처

  • 잘못된 번역을 찾은 사람: kcm1700