Problem: Tag

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

Tag

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:

There are N people playing today, and everyone has a different number between 1 and N inclusive.
At the start of the game, player 1 is on the red team and player 2 is on the blue team. All other players start on no team.
Over the course of the game, people on a team will tag people who are not on a team. The person who has been tagged then joins the team of the person who tagged them.
Note that it is possible some of the players will not have been tagged by the end of the game.

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

Input

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.

Output

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

Sample Output

4 3

Explanation

Initially, player 1 is on the red team and player 2 is on the blue team.
Player 2 tags player 7, now player 7 is also on the blue team. The blue team now has two players.
Player 1 tags player 8, now player 8 is on the red team with player 1. The red team now has two players.
Player 8 tags player 4, now player 4 is on the red team with players 1 and 8. The red team now has three players.
Player 7 tags player 5, now player 5 is on the blue team with players 2 and 7. The blue team now has three players.
Player 8 tags player 6, now player 6 is on the red team with players 1, 8 and 4. The red team now has four players.

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

For Subtask 1 (20 marks), only players 1 and 2 tag other players. That is, a is always equal to either 1 or 2.
For Subtask 2 (20 marks), players only ever make at most one tag. That is, all values of a are distinct.
For Subtask 3 (30 marks), there are at most 1000 players. That is, 2 ≤ N ≤ 1000.
For Subtask 4 (30 marks), no further constraints apply.