Let us label ~M_{ab}^{(k)}~ as the biggest advantage Mirko can achieve on a route with at most ~k~ steps which begins in village ~a~ and ends in village ~b~. The task is to find the minimal ~k_\min~ such that one diagonal element in the matrix ~M^{(k_\min)}~ is strictly positive. We also want to know the maximal such diagonal element in the matrix ~M^{(k_\min)}~, as it is the second required output number.

We can notice that if we know ~M^{(p)}~ and ~M^{(q)}~, we can calculate ~M^{(p+q)}~ with a procedure similar to matrix multiplication. The complexity of this procedure is ~\mathcal O(N^3)~.

These observations let us use binary search for ~k~ and then using fast (matrix) multiplication we calculate ~M^{(k)}~. Unfortunately, the complexity of this procedure is ~\mathcal O(N^3 \log^2 N)~, which wasn't enough for ~100\%~ of points.

In order to achieve maximum points, it was necessary to calculate matrices ~M^{(k)}~ for ~k = 2^0, 2^1, 2^2, \dots~ (complexity ~\mathcal O(N^3 \log N)~) and then find the minimal ~k~ in the procedure which determines its digit by digit in binary notation (from the largest to the smallest digit). The total complexity of this procedure is still ~\mathcal O(N^3 \log N)~ which was sufficient for ~100\%~ of points.