### Woburn Challenge 2018-19 Round 4 - Senior Division

## Problem 3: Dance Royale

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

In *Dance Royale*, there are `N` (1 ≤ `N` ≤ 300,000) locations on a map (numbered from 1 to `N`). Each location `i` has a destination number `D _{i}` (0 ≤

`D`≤

_{i}`N`,

`D`≠

_{i}`i`), which is used during gameplay (as described below).

There are also `M` (2 ≤ `M` ≤ 300,000) players, with the `i`-th player beginning the game at location `L _{i}` (1 ≤

`L`≤

_{i}`N`). Each player has some sick dance moves.

The game proceeds in sets of three phases as follows:

- 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.
- 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`. - 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` ≤ 50, `M` ≤ 50, and `D _{i}` > 0 for each

`i`.

In test cases worth another 6/28 of the points,

`N`≤ 2000, and

`D`> 0 for each

_{i}`i`.

In test cases worth another 10/28 of the points,

`D`> 0 for each

_{i}`i`.

### Input Format

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..

`N`.

`M`lines follow, the

`i`-th of which consists of a single integer,

`L`, for

_{i}`i`= 1..

`M`.

### Output Format

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.

All Submissions

Best Solutions

**Point Value:** 15 (partial)

**Time Limit:** 5.00s

**Memory Limit:** 128M

**Added:** Mar 22, 2019

**Author:** SourSpinach

**Languages Allowed:**

C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

## Comments (Search)

It's quiet in here...