1567번 - 모든 사이클의 길이

어떤 나라는 몇 개의 도시로 이루어져 있다. 몇몇 쌍의 도시는 서로 단방향 도로로 연결되어 있다. (단방향 도로가 A → B, 그리고 B → A 이렇게 총 2가지 존재할 수도 있다.)

세준이는 N개의 도시중 하나를 골라서 출발한다. 세준이가 도로 하나를 지날 때, 하루가 걸린다. 만약 세준이가 어떤 도시에서 시작해서, 정학하게 x개의 도로를 거친 후 시작한 도시로 돌아온다면, 세준이는 길이가 x인 방학친구가 있는 것이다.

방학 문자열은 0과 1로 이루어진 무한한 문자열이다. i번째 문자는(1번부터 시작) i인 방학친구가 있으면 1, 없으면 0이다.

위과 같은 나라가 주어졌을 때, 방학 문자열은 00110111111111.........이다. 0 → 1 → 3 → 0은 길이가 3이고, 0 → 1 → 2 → 3 → 0은 길이가 4이고, 0 → 1 → 3→0 → 1 → 3 → 0은 길이가 6이다. 그런데, 이 무한한 문자열에 주기가 보인다면, 주기를 괄호로 묶어서 간단하게 표현할 수 있다. 따라서, 위의 문자열은 00110(1) 또는, 00110111(11)과 같이 나타낼 수 있지만, 가장 길이가 짧은 것을 선택하기로 한다.

도시의 정보가 주어졌을 때, 방학문자열의 길이가 가장 짧은 것을 출력하는 프로그램을 작성하시오.

첫째 줄에 도시의 개수 N이 주어진다. 둘째 줄부터 N개의 줄에 도로가 있으면 1, 없으면 0이 주어진다.

첫째 줄에 정답을 출력한다.

• 2 ≤ N ≤ 30