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 300\,000)~ 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 300\,000)~ 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 2\,000~, 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.