명제 증명

영선이는 미적분학 시험을 준비하면서 명제 $N$개가 모두 동치임을 증명하려고 한다. 명제에는 0번부터 $N-1$번까지 번호가 붙어 있다.

서로 다른 두 명제 $x$와 $y$에 대해 영선이는 "$x$이면 $y$이다"를 증명할 수 있고, 증명마다 난이도가 정해져 있다. "$x$이면 $y$이다"의 난이도와 "$y$이면 $x$이다"의 난이도는 서로 다를 수 있다.

영선이가 오늘 할 일은 증명을 몇 개 골라서 임의의 두 명제가 직접 또는 다른 명제를 거쳐 서로를 함축하게 만드는 것이다. 예를 들어 $N = 3$이면 0 => 1, 1 => 0, 0 => 2, 2 => 0을 증명하는 방법이 있고, 0 => 1, 1 => 2, 2 => 0을 증명하는 방법도 있다.

이렇게 고른 증명 중에서 가장 어려운 난이도와 가장 쉬운 난이도의 차이를 최소로 만들려고 한다. 그 최솟값을 구하는 프로그램을 작성하시오.

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

다음 $N$개의 줄에는 증명의 난이도가 한 줄에 $N$개씩 주어진다. $i$번째 줄의 $j$번째 정수는 $i$ => $j$를 증명하는 난이도이다. 번호는 0번부터 센다.

난이도는 0 이상 150,000 이하의 정수이고, $i$번째 줄의 $i$번째 정수는 항상 0이다.

모든 명제가 서로를 함축하도록 증명을 골랐을 때, 고른 증명 중 가장 어려운 난이도와 가장 쉬운 난이도의 차이가 가장 작은 경우의 그 차이를 첫째 줄에 출력한다.

$N = 1$이면 증명을 하나도 고르지 않아도 되므로 0을 출력한다.