28101번 - 지구평면설

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

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

이때 각각의 $a_i$가 정수일 필요는 없음에 유의하라.

하지만 찬우는 게으름뱅이라 자신이 곱해야 할 수의 종류가 많아지는 것을 좋아하지 않는다. 따라서 찬우는 $a_1 , a_2 , ... , 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 , ... , a_{2N}$중에서 등장하는 서로 다른 수의 개수의 최솟값을 출력한다. 만약 학교를 평평하게 만들 수 있는 $a_1 , a_2 , ... , a_{2N}$이 존재하지 않는 경우 -1을 출력한다.

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