Table Recovery

시간 제한2초메모리 제한2048 MB

요약

주어진 N x N 격자의 행과 열을 바꿔서 얻을 수 있는 덧셈표 중 사전순으로 가장 작은 것을 복원한다.

난이도: 어려움10점 중 8점
유형: 그래프, 유니온 파인드, 정렬, 완전 탐색
정답자: 아직 제출이 없습니다

문제

Bessie has an $N\times N$ ( $1\le N\le 1000$ ) addition table where the integer in the cell at row $r$ and column $c$ is $r+c$ , for all $1\le r,c\le N$ . For example, for $N=3$ , the table would look like this:

2 3 4
3 4 5
4 5 6

Unfortunately, Elsie got ahold of the table and permuted it by performing the following three types of operations as many times as she wanted.

Swap two rows
Swap two columns
Select two values $a$ and $b$ that are both present in the table, then simultaneously change every occurrence of $a$ to $b$ and every occurrence of $b$ to $a$ .

Elsie will always perform operations in increasing order of type; that is, she performs as many operations as she likes (possibly none) first of type $1$ , then of type $2$ , and finally of type $3$ .

Help Bessie recover a possible state of the table after Elsie finished applying all of her operations of types $1$ and $2$ , but before applying any operations of type $3$ . There may be multiple possible answers, in which case you should output the lexicographically smallest one.

To compare two tables lexicographically, compare the first entries at which they differ, when reading both tables in the natural order (rows from top to bottom, left to right within a row).

입력

The first line contains $N$ .

The next $N$ lines each contain $N$ integers, representing Bessie's addition table after Elsie has permuted it.

출력

The lexicographically minimum possible state of the table after all operations of types 1 and 2, but before any operations of type 3. It is guaranteed that the answer exists.

예제3

예제 1
입력
```
1
2
```
예상 출력
```
2
```
예제 2
입력
```
3
3 4 2
5 2 3
6 3 5
```
예상 출력
```
4 2 3
5 3 4
6 4 5
```

예제 3

입력

6
8 10 5 6 7 4
12 11 10 4 8 2
5 4 6 7 9 8
10 2 4 8 5 12
6 8 7 9 3 5
4 12 8 5 6 10

예상 출력

7 5 8 9 10 6
4 2 5 6 7 3
8 6 9 10 11 7
5 3 6 7 8 4
9 7 10 11 12 8
6 4 7 8 9 5