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

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

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

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

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

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

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

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

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

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

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

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

Connecting Supertrees timer 1초 memory 2048MB

Connecting Supertrees 1초 2048MB