Thornhill Computer Club 2023 - September Contest - Problem 3

JoePeewee has recently been addicted to rock paper scissors. In this game, you can play against one other player, and both choose to play either Rock, Paper, or Scissors. The following pairs of choices can occur which decides who won:

• Rock beats Scissors
• Scissors beats Paper
• Paper beats Rock

If you both pick the same choice no one is eliminated.

Because of his unique obsession with Rock, Paper, Scissors, he has decided to host the largest tournament of Rock, Paper, Scissors in the world, bringing in as many players as he could find. Since there are so many people playing, a new way of determining who wins must be implemented.

In this version of Rock, Paper, Scissors, everyone chooses one other player to attack. If their attack beats the other's, the player they chose is eliminated, otherwise, if their attack loses to the other player, they are eliminated. Every round there will be ~N~ players each numbered from ~1 - N~. Each player also chooses another number ~P_i~ representing the number of the player they are targeting and a character ~A_i~ representing the attack they chose. R for rock, P for paper, or S for scissors. A player can still be eliminated even if their attacker is eliminated by another player, this means it is possible for every player in the game to be eliminated at once.

Due to the abundance of players, however, JoePeewee in fact cannot count how many people were eliminated.

Can you help JoePeewee by determining how many people were eliminated by the end of a single round of rock, paper, scissors!

Input Specifications

The first line consists of a single integer ~N~ ~(2 \le N \le 100,000)~ representing the number of players participating.
The next ~N~ lines consist of an integer ~P_i~ representing ~N~th player target and a character ~A_i~ representing their attack of choice.

Output Specification

Output the number of players that were eliminated.

Sample Input 1

3
2 R
1 P
2 S

Sample Output 1

2

Explanation of Sample Output 1

The players have chosen the following attacks: Player 1 chose R, Player 2 chose P, and Player 3 chose S.

Since Player 1 decided to attack Player 2, Player 1 is eliminated (Since Paper beats Rock).
Player 2 also decided to attack Player 1, In this case Player 1 is already eliminated.
Player 3 decided to attack Player 2, causing Player 2 to be eliminated (Since Scissors beats Paper).
Notice how Player 1 was still eliminated although their attacker, Player 2 was also eliminated)

Sample Input 2

5
2 R
5 P
2 S
3 S
1 R

Sample Output 2

3

Explanation of Sample Output 2

Player 1 is eliminated after attacking Player 2.
Player 2 eliminates Player 5.
Player 3 eliminates Player 2.
Player 3 is safe since they are not attacking anyone or being attacked by anyone with rock. Player 4 is safe since they are not attacking anyone or being attacked by anyone with rock.