시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 14 5 3 30.000%

문제

영선이는 미적분학 시험을 준비하고 있다. 오늘 시험공부하고 있는 내용은 N개의 명제가 모두 동치임을 증명하는 것이다. 명제는 0번부터 N-1번까지 번호가 매겨져 있다.

모든 명제의 쌍 x와 y에 대해서, 영선이는 "x이면 y이다"를 등명할 수 있다. 하지만, 이러한 증명은 모두 서로 다른 난이도를 가지고 있다.

오늘 해볼 것은 모든 명제를 직접 또는 간접적으로 서로를 함축하고 있다는 것을 증명하는 것이다. 예를 들어, N = 3인 경우에 가능한 한 가지 방법은 0 => 1, 1 => 0, 0 => 2, 2 => 0을 증명하는 것이다. 또다른 방법으로는 0 => 1, 1 => 2, 2 => 0을 증명하는 것이다.

모든 명제를 서로 함축하고 있게 증명할 때, 가장 어려운 난이도와 쉬운 난이도의 차이의 최소값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 명제의 개수 N (1 ≤ N ≤ 50)이 주어진다.

둘째 줄부터 N개의 줄에는 증명의 난이도가 주어진다. i번 줄의 j번 정수는 i => j를 증명하는 난이도이다.

난이도는 0보다 크거나 같고, 150,000보다 작거나 같은 정수이고, i번째 줄의 i번째 수는 0이다.

출력

모든 명제를 서로 함축하고 있게 증명할 때, 가장 어려운 난이도와 쉬운 난이도의 차이의 최소값을 출력한다.

예제 입력 1

4
0 11 13 13
10 0 12 13
10 10 0 11
12 10 10 0

예제 출력 1

1

예제 입력 2

5
0 1000 1000 1000 1000
1 0 1000 1000 1000
1 1 0 1000 1000
1 1 1 0 1000
1 1 1 1 0

예제 출력 2

999

예제 입력 3

4
0 136946 89305 28946 
40152 0 150000 85407 
122920 110420 0 32811 
2092 79717 53028 0

예제 출력 3

50771