AIOC Banner

Problem: Tag

Want to try solving this problem? You can submit your code online if you log in or register.


Time Limit: 1 second
Memory Limit: 1 GB
Input File: tagin.txt
Output File: tagout.txt

Thank you for being the scorer for our game of tag. The rules are pretty simple:

As scorer, we need you to figure out how many people are on each team at the end of the game.


The first line of input will contain two integers N and M: the number of players in the game and the number of tags that occur during the game, respectively. M lines will follow, describing the tags that happen in chronological order. Each line will contain two integers a and b. This indicates that player a tags player b, so now player b joins player a's team. It is guaranteed that, prior to this tag, player a is already on a team and player b is not.


Your program must output two integers on one line. The number of players on the red team at the end of the match, and the number of players on the blue team at the end of the match.

Sample Input

8 5
2 7
1 8
8 4
7 5
8 6

Sample Output

4 3


At the end of this, the red team consists of four players 1, 8, 6, and 4. The blue team consists of three players 2, 7, and 5. Note that player 3 was never tagged so is on neither team at the end of the match.

Subtasks & Constraints

For all subtasks, 2 ≤ N ≤ 100 000, 0 ≤ M ≤ N-2, and 1 ≤ a, b ≤ N


Privacy statement
© Australian Mathematics Trust 2001-2023

Page generated: 25 March 2023,  5:49pm AEDT