Duty Of Call

View as PDF

Submit solution

Points: 10 (partial)
Time limit: 2.0s
Java 8 5.0s
Memory limit: 256M

Problem type

Soupy boy wants to play duty of call with bruce! Thus, the students in olympiads have become the players! They are split into 2 teams, each given a sniper rifle. Being the competitive person the players are, the players lock on to other player(s) and instantly fires their sniper rifle, eliminating the other player(s). It is guaranteed that no friendly fire occurred.

You as a judge, are given the job of announcing how many players on each team are left standing. However, you haven't been paying attention since you were busy grinding problems, you don't know who is on which team! Luckily, you have one friend and you know he is on soupy boy's team. Can you find a way to find out how many players on each team are still left standing?

Note: It is possible for a player to lock on to multiple targets.

Input Specification

First line, two integers N, R, denoting the number of players in the competition and which player is known to be on soupy boy's team. The next N lines each describe the actions of one of the players. The K^{th} line begins with an integer M followed by M integers, the targets of player K. Players are numbered from 1 to N.

Output Specification

Output two integers, the number of players that weren’t hit on soupy boy's team followed by bruce's team. It is guaranteed that knowing that player R is on soupy boy's is enough to uniquely determine the two teams.

Subtasks

For all subtasks, 1 \le R \le N \le 5 \times 10^5. The total number of shots fired will not exceed 10^7.

Subtask 1 [15%]

1 \le R \le N \le 100

The total number of shots fired will not exceed 10^3.

Subtasks 2 [25%]

1 \le R \le N \le 10^4

The total number of shots fired will not exceed 10^5.

Subtask 3 [60%]

No additional constraints.

Sample Input 1

4 3
1 2
1 3
1 4
0

Sample Output 1

1 0

Explanation Of Sample 1

In the first case, players 1 and 3 are on soupy boy's team and players 2 and 4 are on bruce's team. All but player 1 get eliminated.

Sample Input 2

7 3
2 2 3
1 4
2 1 4
1 6
1 3
1 4
1 4

Sample Output 2

1 1

Explanation Of Sample 2

In the second case, players 2, 3, 6, 7 are on soupy boy's team and players 1, 4, 5 are on bruce's team. All but players 7 and 5 are eliminated.


Comments

There are no comments at the moment.