지구평면설

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

요약

N x N 격자의 모든 칸을 같은 값으로 만들도록 행과 열에 곱할 0이 아닌 수를 고르고, 서로 다른 곱셈 값의 개수를 최소화합니다.

난이도: 보통10점 중 6점
유형: 해시맵, 수학, 행렬
정답자: 아직 제출이 없습니다

문제

찬우는 지구평면설을 지지한다. 그래서 그는 이를 증명하려고 포스텍을 평평하게 만들 것이다! 포스텍의 지면 높이 분포는 $N \times N$ 행렬로 표현된다. 찬우는 모든 $i$ 에 대해 아래의 두 작업을 모두 수행해서 포스텍의 제각각인 지면 높이를 전부 같게 만들려고 한다.

$i$ 번째 행의 모든 수에 $0$ 이 아닌 임의의 수 $a_{2i-1}$ 를 곱한다.
$i$ 번째 열의 모든 수에 $0$ 이 아닌 임의의 수 $a_{2i}$ 를 곱한다.

각 $a_i$ 가 정수일 필요는 없다.

하지만 찬우는 게으름뱅이라서 곱해야 할 수의 종류가 늘어나는 것을 싫어한다. 그래서 $a_1, a_2, \ldots, a_{2N}$ 의 값을 적절히 정해, 수열에 등장하는 서로 다른 수의 개수가 최소가 되도록 하고 싶어 한다. 찬우를 위해 수열 $a$ 에 등장하는 수의 종류를 최소로 만들어 주자!

입력

첫 번째 줄에 $N$ 이 주어진다. ( $1 \le N \le 1\,000$ )

두 번째 줄부터 $N$ 개의 줄에 걸쳐, 각 줄마다 $N$ 개의 정수 $h_{ij}$ 가 공백으로 구분되어 주어진다. $h_{ij}$ 는 $i$ 행 $j$ 열에 있는 포스텍의 지면 높이이다. ( $1 \le i, j \le N$ ; $1 \le h_{ij} \le 10^9$ )

출력

조건을 만족하는 $a_1, a_2, \ldots, a_{2N}$ 에 등장하는 서로 다른 수의 개수의 최솟값을 출력한다. 포스텍을 평평하게 만들 수 있는 $a_1, a_2, \ldots, a_{2N}$ 이 없으면 -1을 출력한다.

힌트

⚠️ 실제 포스텍의 환경과 다릅니다. ⚠️

예제3

예제 1
입력
```
2
1 2
2 4
```
예상 출력
```
2
```
예제 2
입력
```
3
1 2 3
2 5 8
3 7 10
```
예상 출력
```
-1
```

예제 3

입력

예상 출력