31116번 - Hamilton 스페셜 저지다국어

문제

Bobo has an $n \times n$ symmetric matrix $C$ consisting of zeros and ones. For a permutation $p_1, \dots, p_n$ of 1,ドル \dots, n,ドル let $$ c_i = \begin{cases} C_{p_i, p_{i + 1}} & \text{for } 1 \leq i < n \\ C_{p_n, p_1} & \text{for } i = n \\ \end{cases}\text{.}$$

The permutation $p$ is almost monochromatic if and only if the number of indices $i$ (1ドル \leq i < n$) where $c_i \neq c_{i + 1}$ is at most one.

Find an almost monochromatic permutation $p_1, \dots, p_n$ for the given matrix $C$.

입력

The input consists of several test cases terminated by end-of-file. For each test case,

The first line contains an integer $n$.

For the following $n$ lines, the $i$-th line contains $n$ integers $C_{i, 1}, \dots, C_{i, n}$.

출력

For each test case, if there exists an almost monochromatic permutation, output $n$ integers $p_1, \dots, p_n$ which denote the permutation. Otherwise, output $-1$.

If there are multiple almost monochromatic permutations, any of them is considered correct.

제한

• 3ドル \le n \le 2000$
• $C_{i, j} \in \{0, 1\}$ for each 1ドル \leq i, j \leq n$
• $C_{i, j} = C_{j, i}$ for each 1ドル \leq i, j \leq n$
• $C_{i, i} = 0$ for each 1ドル \leq i \leq n$
• In each input, the sum of $n$ does not exceed 2000ドル$.

노트

For the first test case, $c_1 = C_{3, 1} = 1,ドル $c_2 = C_{1, 2} = 0,ドル $c_3 = C_{2, 3} = 0$. Only when $i = 1,ドル $c_i \neq c_{i + 1}$. Therefore, the permutation 3,ドル 1, 2$ is an almost monochromatic permutation.