25735번 - Similarity Graph 스페셜 저지다국어

문제

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

Similarity graph of $p$ and $q,ドル $S(p,q),ドル is defined as following:

• $S(p,q)$ has $N$ labeled vertices, numbered from 1ドル$ to $N$.
• There is a edge between vertex $i$ and $j$ if and only if $p_i<p_j$ and $q_i<q_j$ are both true, or both 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\},ドル satisfying $S(p,q) =G$.

입력

The first line contains one integer, $N$.

The next $N$ lines contain space-separated $N$ integers. The $j$-th integer of 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 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.

제한

• 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<j\le N$)
• $E(i,i) =0$ (1ドル\le i\le N$)

힌트