In a LAN, $n^2$ routers are connected in an $n \times n$ mesh such that $R(i, j)$ represents a router in the $i$-th row and $j$-th column of the mesh.
- Find how many distinct shortest paths exist between two routers $R(i_1, j_1)$ and $R(i_2, j_2) \: (1 \leq i_1, j_1, i_2, j_2 \leq n)$. Two paths are distinct if they differ in at least one link.
- At most how many of these distinct shortest paths will be node disjoint, i.e., with no common node except the source and the destination? Justify your answer.