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$)