슈퍼트리 연결

가든스 바이 더 베이는 싱가포르에 있는 대형 자연공원이다. 이 공원에는 슈퍼트리라고 부르는 타워가 $n$개 있고, 0부터 $n-1$까지 번호가 붙어 있다. 다리를 0개 이상 건설한다. 각 다리는 서로 다른 두 타워를 잇고, 양방향으로 건널 수 있다. 같은 두 타워를 잇는 다리는 두 개 이상 놓을 수 없다.

타워 $x$에서 타워 $y$로 가는 경로는 다음 조건을 모두 만족하는 1개 이상의 타워 수열이다.

• 수열의 첫 원소는 $x$이다.
• 수열의 마지막 원소는 $y$이다.
• 수열의 모든 원소는 서로 다르다.
• 수열에서 연속한 두 원소는 다리로 연결되어 있다.

정의상 타워에서 자기 자신으로 가는 경로는 정확히 하나다. 타워 $i$에서 $j$로 가는 경로 수는 타워 $j$에서 $i$로 가는 경로 수와 같다.

설계자는 모든 $0 \le i, j \le n-1$에 대해 타워 $i$에서 $j$로 가는 서로 다른 경로가 정확히 $p[i][j]$개가 되도록 다리를 놓기를 원한다. 이때 $0 \le p[i][j] \le 3$이다. 이 요구를 만족하는 다리 배치를 구하거나, 불가능한 경우 그 사실을 판정하라.

• $1 \le n \le 1000$
• 모든 $0 \le i \le n-1$에 대해 $p[i][i] = 1$
• 모든 $0 \le i, j \le n-1$에 대해 $p[i][j] = p[j][i]$
• 모든 $0 \le i, j \le n-1$에 대해 $0 \le p[i][j] \le 3$