Woburn Challenge 2018-19 Round 4 - Senior Division

Billy is trying his hand at the latest popular game taking the world by storm: Dance Royale.

In Dance Royale, there are $N$ $(1\le N\le 300000)$ locations on a map (numbered from $1$ to $N$). Each location $i$ has a destination number $D_i$ $(0\le D_i\le N,D_i\ne i)$, which is used during gameplay (as described below).

There are also $M$ $(2\le M\le 300000)$ players, with the $i$-th player beginning the game at location $L_i$ $(1\le L_i\le N)$. Each player has some sick dance moves.

The game proceeds in sets of three phases as follows:

1. For each unordered pair of players still in the game, if they are currently at the same location and have not yet had a dance-off against one another, then they engage in a dance-off against one another. Nobody is harmed in the process, a good time is simply had.
2. For each player still in the game, let $d$ be their current location's destination number. If $d=0$, then they're forced to permanently leave the game. Otherwise, they move to location $d$.
3. If there are fewer than $2$ players left in the game, then the game ends. Otherwise, the process repeats itself from phase $1$.

Note that the game may last forever, which is fine — Billy is accustomed to extended periods of mental focus.

After the game has either ended or has gone on for an infinite amount of time, how many dance-offs will end up having taken place in total?

Subtasks

In test cases worth $6/28$ of the points, $N\le 50$, $M\le 50$, and $D_i>0$ for each $i$.
In test cases worth another $6/28$ of the points, $N\le 2000$, and $D_i>0$ for each $i$.
In test cases worth another $10/28$ of the points, $D_i>0$ for each $i$.

Input Specification

The first line of input consists of two space-separated integers, $N$ and $M$.
$N$ lines follow, the $i$-th of which consists of a single integer, $D_i$, for $i=1\dots N$.
$M$ lines follow, the $i$-th of which consists of a single integer, $L_i$, for $i=1\dots M$.

Output Specification

Output a single integer, the number of dance-offs which will take place.

Sample Input 1

4 4
4
3
1
3
4
2
3
4

Sample Output 1

3

Sample Input 2

5 6
4
0
4
1
1
4
2
5
3
2
2

Sample Output 2

4

Sample Explanation

In the first case:

• Right off the bat, a dance-off will occur between players $1$ and $4$, as they both occupy location $4$.
• Then, in the second cycle of the phases, players $1$, $2$, and $4$ will all find themselves at location $3$, resulting in player $2$ having dance-offs with both players $1$ and $4$. Note that players $1$ and $4$ will not repeat their dance-off against one another.
• The game will end up continuing forever with all $4$ players in action, but no more dance-offs will ever take place.

In the second case:

• Right off the bat, dance-offs will occur between player pairs $(2,5)$, $(2,6)$, and $(5,6)$, due to players $2$, $5$, and $6$ all occupying location $2$. These $3$ players will then leave the game in phase $2$.
• Then, in the second cycle of the phases, players $1$ and $3$ will both find themselves at location $1$ and will therefore have a dance-off.
• The game will end up continuing forever with $3$ players remaining, but no more dance-offs will ever take place.