ISL 2020 N2

For each prime $p$, there is a kingdom of $p$-Landia consisting of $p$ islands numbered $1,2, \ldots, p$. Two distinct islands numbered $n$ and $m$ are connected by a bridge if and only if $p$ divides $\left(n^{2}-m+1\right)\left(m^{2}-n+1\right)$. The bridges may pass over each other, but cannot cross. Prove that for infinitely many $p$ there are two islands in $p$-Landia not connected by a chain of bridges. (Denmark)