FPC23-033.Feline Friendship

There is a big community of $n$ cats in Delft. The cats are numbered from $1$ to $n$. Each cat has a favourite playing partner, $p_i$ (cats can be very egocentric, so $p_i = i$ is allowed). It turns out that no two cats share the same favourite playing partner, so the $p_i$ are distinct.

You are organising a big game of Cats versus Coatis football (Non-American.), for which you will need exactly $k$ cats in a team.

To get $k$ cats to join your game, you appoint one cat as team captain. Then the following process is repeated, starting with the team captain cat. A cat $i$ selects its favourite playing partner $p_i$, adding $p_i$ to the team. Subsequently, cat $p_i$ will select its favourite playing partner, adding $p_{p_i}$ to the team, and so on. The process only stops when a cat tries to invite a cat that is already on the team. If, for some choice of the team captain, the number of cats in the team is exactly $k$, the game can be played.

Sometimes, it is not possible to find a team of $k$ cats in this way. Therefore, you have decided to convince some cats to change their favourite playing partner. Formally, you repeatedly select a cat $i$ ($1 \leq i \leq n$) and choose an $x$ ($1 \leq x\leq n$) and update the playing partner $p_i \mathrel{\mathop:}= x$ After the change, it can be the case that $p_1, p_2, p_3, \dots , p_n$ are no longer distinct, but that is fine.

What is the minimum number of times you need to convince a cat to change their favourite playing partner, such that the football game can be played?