유사 그래프

시간 제한1초메모리 제한1024 MB

요약

정점이 N개인 그래프가 주어졌을 때, 이 그래프와 같은 유사도 그래프를 만드는 두 순열 p, q를 찾고, 없으면 NO를 출력합니다.

문제

$p$ 와 $q$ 를 $\{1,2,\dots,N\}$ 의 두 순열이라고 하자.

$p$ 와 $q$ 의 유사 그래프 $S(p,q)$ 는 다음과 같이 정의한다.

$S(p,q)$ 는 1번부터 $N$ 번까지 번호가 붙은 $N$ 개의 정점을 가진다.
정점 $i$ 와 정점 $j$ 사이에 간선이 있는 것은 $p_i<p_j$ 와 $q_i<q_j$ 가 모두 참이거나 모두 거짓일 때뿐이다. ( $1\leq i<j\leq N$ )

1번부터 $N$ 번까지 번호가 붙은 $N$ 개의 정점을 가진 단순 무방향 그래프 $G$ 가 주어진다. $S(p,q)=G$ 를 만족하는 순열 쌍 $(p,q)$ 를 구하시오.

첫째 줄에 정수 $N$ 이 주어진다.

다음 $N$ 개 줄에는 공백으로 구분된 정수 $N$ 개가 한 줄씩 주어진다. $i$ 번째 줄의 $j$ 번째 정수는 $E(i,j)$ 이다. $E(i,j)$ 는 정점 $i$ 와 정점 $j$ 사이에 간선이 있으면 1, 없으면 0이다.

조건을 만족하는 $(p,q)$ 가 없으면 NO를 출력한다.

그렇지 않으면 첫째 줄에 YES를 출력하고, 다음 두 줄에 각각 $p$ 와 $q$ 를 출력한다. 답이 여러 개이면 그중 아무것이나 출력해도 된다.

예제 1

입력

예상 출력

YES
1 2 3 4
2 4 1 3

예제 2

입력

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

예상 출력

NO