## WC '18 Contest 4 S3 - Dance Royale

View as PDF

Points: 15 (partial)
Time limit: 2.5s
Memory limit: 128M

Author:
Problem type
##### 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 locations on a map (numbered from to ). Each location has a destination number , which is used during gameplay (as described below).

There are also players, with the -th player beginning the game at location . 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 be their current location's destination number. If , then they're forced to permanently leave the game. Otherwise, they move to location .
3. If there are fewer than players left in the game, then the game ends. Otherwise, the process repeats itself from phase .

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?

In test cases worth of the points, , , and for each .
In test cases worth another of the points, , and for each .
In test cases worth another of the points, for each .

#### Input Specification

The first line of input consists of two space-separated integers, and .
lines follow, the -th of which consists of a single integer, , for .
lines follow, the -th of which consists of a single integer, , for .

#### 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 and , as they both occupy location .
• Then, in the second cycle of the phases, players , , and will all find themselves at location , resulting in player having dance-offs with both players and . Note that players and will not repeat their dance-off against one another.
• The game will end up continuing forever with all 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 , , and , due to players , , and all occupying location . These players will then leave the game in phase .
• Then, in the second cycle of the phases, players and will both find themselves at location and will therefore have a dance-off.
• The game will end up continuing forever with players remaining, but no more dance-offs will ever take place.