모든 순환 이동 길이

어떤 나라에는 N개의 도시가 있고, 도시 쌍 사이에 단방향 도로가 있을 수 있다. 두 도시 사이에 서로 반대 방향의 도로가 모두 존재할 수도 있다.

여행자는 한 도시에서 출발해 하루에 도로 하나를 지난다. 어떤 도시에서 출발하여 정확히 x개의 도로를 지난 뒤 다시 출발한 도시로 돌아올 수 있다면, 길이 x의 순환 이동이 가능하다고 하자.

순환 문자열은 0과 1로 이루어진 무한 문자열이다. 문자는 1번부터 세며, i번째 문자는 길이 i의 순환 이동이 가능하면 1, 불가능하면 0이다.

이 문자열은 어느 시점부터 주기적으로 반복된다. 반복되는 부분을 괄호로 묶어 00110(1)처럼 나타낼 수 있다. 같은 무한 문자열을 여러 방식으로 나타낼 수 있다면, 괄호 밖 문자 수와 괄호 안 문자 수의 합이 가장 작은 표현을 선택한다. 합이 같다면 괄호 밖 부분이 더 짧은 표현을 선택하고, 그래도 같다면 괄호 안 부분이 더 짧은 표현을 선택한다.

도시 정보가 주어질 때 순환 문자열의 가장 짧은 표현을 출력하라.

첫째 줄에 도시의 개수 N이 주어진다.

다음 N개의 줄에는 길이 N의 0과 1로 이루어진 문자열이 주어진다. i번째 줄의 j번째 문자가 1이면 i번 도시에서 j번 도시로 가는 단방향 도로가 있고, 0이면 없다.

순환 문자열의 가장 짧은 표현을 한 줄에 출력한다. 반복되는 부분은 괄호로 묶어 출력한다.

• 2 ≤ N ≤ 30
• 도시는 입력에 등장하는 순서대로 1번부터 N번까지 번호가 붙어 있다고 생각한다.
• 각 도로 정보 문자는 0 또는 1이다.