\begin{enumerate}
\item ($8$ points): $k = 1$;
\item ($17$ points): $p_i = i$;
\item ($26$ points): $n \le 2000, k \le 2000$;
\item ($28$ points): $n \le 2000$, for any $i$ and $j$, there exists a $k$ such that $p[p[p \dots p[i] \dots ]]=j$, where the nesting is taken $k$ times;
\item ($9$ points): for any $i$ and $j$, there exists a $k$ such that $p[p[p \dots p[i] \dots ]]=j$, where the nesting is taken $k$ times;
\item ($12$ points): without additional restrictions.
\end{enumerate}