Flat Earth

Time limit2sMemory limit1024 MB

Summary

Choose nonzero row and column multipliers that make every cell of an N x N grid equal, minimizing the number of distinct multiplier values.

Level: Medium6 of 10
Topics: Hash map, Math, Matrix
Solved: No attempts yet

Problem

Chanwoo supports the flat Earth theory. To prove it, he will flatten POSTECH! The ground height distribution of POSTECH is represented by an $N \times N$ matrix. For every $i$ , Chanwoo performs both of the following operations to make all the uneven ground heights of POSTECH equal.

Multiply every number in row $i$ by a nonzero number $a_{2i-1}$ of your choice.
Multiply every number in column $i$ by a nonzero number $a_{2i}$ of your choice.

Note that each $a_i$ does not need to be an integer.

Chanwoo is lazy and does not want more kinds of multipliers to handle. He wants to choose $a_1, a_2, \ldots, a_{2N}$ so that the number of distinct values among them is as small as possible. Help Chanwoo minimize the number of distinct values in the sequence $a$ !

Input

The first line contains $N$ ( $1 \le N \le 1\,000$ ).

From the second line on, $N$ lines follow, each containing $N$ integers $h_{ij}$ separated by spaces. $h_{ij}$ is the ground height at row $i$ , column $j$ of POSTECH. ( $1 \le i, j \le N$ ; $1 \le h_{ij} \le 10^9$ )

Output

Print the minimum number of distinct values among $a_1, a_2, \ldots, a_{2N}$ that satisfy the conditions. If no sequence $a_1, a_2, \ldots, a_{2N}$ can flatten POSTECH, print -1.

Hint

⚠️ This differs from the actual POSTECH environment. ⚠️

Examples3

Example 1
Input
```
2
1 2
2 4
```
Expected output
```
2
```
Example 2
Input
```
3
1 2 3
2 5 8
3 7 10
```
Expected output
```
-1
```

Example 3

Input

Expected output