Proving Propositions

Yeongseon is studying for a calculus exam and wants to prove that $N$ propositions are all equivalent. The propositions are numbered from 0 to $N-1$.

For any two different propositions $x$ and $y$, Yeongseon can prove "if $x$ then $y$", and every such proof has its own difficulty. The difficulty of "if $x$ then $y$" and the difficulty of "if $y$ then $x$" may differ.

Today's task is to choose a set of proofs so that any two propositions imply each other, either directly or through other propositions. For example, when $N = 3$, one way is to prove 0 => 1, 1 => 0, 0 => 2, 2 => 0. Another way is to prove 0 => 1, 1 => 2, 2 => 0.

Among the chosen proofs, Yeongseon wants the gap between the hardest difficulty and the easiest difficulty to be as small as possible. Write a program that finds that minimum gap.

The first line contains the number of propositions $N$ ($1 \le N \le 50$).

Each of the next $N$ lines contains $N$ integers, the difficulties of the proofs. The $j$-th integer on the $i$-th line is the difficulty of proving $i$ => $j$. Numbering starts at 0.

Every difficulty is an integer between 0 and 150,000, and the $i$-th integer on the $i$-th line is always 0.

Print on the first line the smallest possible difference between the hardest and the easiest difficulty among the chosen proofs, over all choices that make every proposition imply every other one.

When $N = 1$, no proof is needed, so print 0.