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.