보행의 개수
시간 제한2초메모리 제한512 MB
인접 행렬로 주어진 방향 그래프에서 길이 L인 보행의 수가 O(L^K)로 증가하는 최소 K를 구하고, 그런 K가 없으면 -1을 출력합니다.
문제
그래프의 보행은 같은 정점과 같은 간선을 여러 번 지나도 되는 경로다. 보행의 길이는 그 보행에 들어 있는 간선의 개수다.
그래프가 주어졌을 때, 길이가 인 보행의 개수가 가 되는 음이 아닌 정수 중에서 가장 작은 값을 구하는 프로그램을 작성하시오.
보행의 개수가 라는 말은, 모든 양의 정수 에 대해 길이가 인 보행의 개수가 이하가 되는 상수 가 존재한다는 뜻이다.
입력
첫째 줄에 그래프의 정점 개수 이 주어진다.
둘째 줄부터 개의 줄에 그래프의 간선 정보가 인접 행렬로 주어진다. 번째 줄의 번째 문자가 Y이면 정점 에서 정점 로 가는 간선이 있고, N이면 그런 간선이 없다. 자기 자신으로 가는 간선은 없다.
출력
첫째 줄에 조건을 만족하는 가장 작은 음이 아닌 정수 를 출력한다. 조건을 만족하는 가 없으면 -1을 출력한다.
힌트
정점 세 개가 서로 양쪽 방향으로 모두 이어져 있으면 길이가 인 보행의 개수는 이다. 이 값은 어떤 로도 로 나타낼 수 없다.
사이클이 하나도 없는 그래프에서는 이 이상이면 보행의 개수가 0이다.
그래프가 서로 떨어진 사이클로만 이루어져 있으면 모든 에 대해 보행의 개수가 과 같다.