Similarity Graph

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

The 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 an edge between vertex $i$ and vertex $j$ if and only if both $p_i<p_j$ and $q_i<q_j$ are true, or both are false. ($1\leq i<j\leq N$)

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,\dots,N\}$ that satisfies $S(p,q)=G$.

The first line contains one integer $N$.

The next $N$ lines each contain $N$ space-separated integers. The $j$-th integer on the $i$-th line is $E(i,j)$. $E(i,j)$ is $1$ if there is an edge between vertex $i$ and vertex $j$, and $0$ otherwise.

If no pair $(p,q)$ satisfies the condition, output NO.

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

• $1\leq N\leq 100$
• $0\leq E(i,j)\leq 1$ ($1\leq i,j\leq N$)
• $E(i,j)=E(j,i)$ ($1\leq i<j\leq N$)
• $E(i,i)=0$ ($1\leq i\leq N$)