I. Similarity Graph
time limit per test
1 second
memory limit per test
1024 mebibytes
input
standard input
output
standard output

Let $$$p$$$ and $$$q$$$ be two permutations of $$$\{1, 2, \ldots, N\}$$$.

A similarity graph of $$$p$$$ and $$$q$$$, $$$S(p,q)$$$, is defined as follows:

  • $$$S(p,q)$$$ has $$$N$$$ labeled vertices, numbered from $$$1$$$ to $$$N$$$.
  • There is a edge between vertices $$$i$$$ and $$$j$$$ ($$$1\leq i \lt j\leq N$$$) if and only if $$$p_i \lt p_j$$$ and $$$q_i \lt q_j$$$ are both true, or both false.

You are given a simple undirected graph $$$G$$$ with $$$N$$$ labeled vertices, numbered from $$$1$$$ to $$$N$$$.

Find a pair $$$(p, q)$$$ of permutations of $$$\{1, 2, \ldots, N\}$$$ satisfying $$$S(p,q) = G$$$.

Input

The first line contains one integer, $$$N$$$.

Each of the next $$$N$$$ lines contains $$$N$$$ space-separated integers. The $$$j$$$-th integer of the $$$i$$$-th line, $$$E(i, j)$$$, is $$$1$$$ if there is an edge between vertices $$$i$$$ and $$$j$$$, or $$$0$$$ otherwise.

  • $$$1 \le N \le 100$$$
  • $$$0 \le E(i, j) \le 1$$$ ($$$1 \le i, j \le N$$$)
  • $$$E(i, j) = E(j, i)$$$ ($$$1 \le i \lt j \le N$$$)
  • $$$E(i, i) = 0$$$ ($$$1 \le i \le N$$$)
Output

If it is impossible to find $$$p$$$ and $$$q$$$ satisfying the condition, output NO.

Otherwise, output YES on the first line. On the following two lines, output $$$p$$$ and $$$q$$$. If there are multiple answers, output any one of them.

Examples
Input
4
0 1 0 1
1 0 0 0
0 0 0 1
1 0 1 0
Output
YES
1 2 3 4
2 4 1 3
Input
6
0 1 0 1 0 1
1 0 0 0 1 0
0 0 0 1 1 1
1 0 1 0 0 0
0 1 1 0 0 0
1 0 1 0 0 0
Output
NO