Connecting Supertrees timer 1초 memory 2048MB

Gardens by the Bay는 싱가포르에 있는 공원이다.

이 공원에는 슈퍼트리라는 이름의 n개의 탑이 있다.

이 탑은 0부터 n - 1까지 번호가 매겨져 있다.

우리는 0개 이상의 다리를 지으려고 한다.

각각의 다리는 서로 다른 두 탑을 잇고, 양방향으로 건널 수 있다.

한 쌍의 탑을 잇는 다리는 최대 하나이다.

탑 x에서 탑 y로의 경로는 다음 조건을 만족하는 하나 또는 그 이상 탑의 서열이다.

• 서열의 첫번째 원소는 x이다.

• 서열의 마지막 원소는 y이다.

• 동일한 원소가 서열에서 두 번 이상 나오는 경우는 없다.

• 서열에서 인접한 두 원소 (탑)은 다리 하나로 연결되어 있다.

정의에 의해서 탑 하나에서 자기 자신으로 가는 경로의 수는 정확하게 하나이며, 

탑 i에서 탑 j로 가는 경로의 가짓수는 탑 j에서 탑 i로 가는 경로의 가짓수와 같다는데 유의하라.

설계를 담당한 책임자는, 다음 조건을 만족하게 다리를 지으려고 한다:

모든 0 ≤ i, j ≤ n - 1에 대해서, 탑 i에서 탑 j로 가는 서로 다른 경로가 정확하게 p_{(​i, j)}가지이다. 0 ≤ p_{(i, j)} ≤ 3이다.

설계 요구 사항을 만족하게 다리를 짓거나, 이것이 불가능하다는 것을 판정하는 프로그램을 작성하시오.​