Teamface
Teamface is the new social network from NewPie High School, whose purpose is to increase collaboration among team members from all their sport teams. This new application is one of the new actions taken to conquer all national championships and ratify NewPie’s place as the top school in the country.
In Teamface, members of teams can befriend each other under the following rules:
- There are N students in NewPie teams (N > 0), identified with numbers 1, 2, ..., N.
- A student can belong to only one of the T NewPie teams (T > 0).
- All teams have the same number of members, M (2 ≤ M ≤ N).
- Every team has exactly one captain (one of its members).
- All members of a given team are Teamface friends among them. They can share strategies, post-match comments and watch replays online.
- A student must have less than ⌊M/2⌋ friends not in his/her team (this is meant to prevent distractions).
Following the NewPie honor code, all players are registered in Teamface and have added their friends according to these rules.
This year’s sponsors have requested the list of players for each team in order to send the training uniforms for the next training session, to be held on Monday. They need a list that contains, for each team, the number of training uniforms of each size. Information about team names and team captains was received correctly, but due to an administrative error at NewPie, the players’ information was apparently incomplete. Indeed, NewPie sent, for each player, his/her identifier, size, and a list with the Teamface friends’ identifiers.
Today is Saturday afternoon and nobody at NewPie can answer any question. But your boss, one of the NewPie sponsors, realized that it is possible to build the required list without any further information. He has chosen you to do this as soon as possible.
Input
There are several cases to solve. Each case begins with a line with two integer numbers T and N, indicating the number of teams and the number of students, respectively (1 ≤ T ≤ 100, 1 ≤ N ≤ 5000). Then, T lines follow, each one containing a non-empty string w and an integer number i (1 ≤ i ≤ N), where w represents the name of a NewPie Team and i represents the identifier of its captain. You may assume that w does not contain any blank and that its length does not exceed 30 characters. This is followed by N lines, one per NewPie student. Each one of these lines contains the student’s identifier j (1 ≤ j ≤ N), his/her uniform size as an integer sj (1 ≤ sj ≤ 50), an integer number fj indicating how many friends j has (0 ≤ fj < N), and the list containing the identifiers of his/her Teamface friends (that list does not have repeated elements and does not include the identifier j). Every line in the input has no leading blanks and its corresponding data is separated by one blank. The input ends with a line with two ‘0’ values.
2/3 Output
The output for each case starts with “Case i:” on a single line, where i is the case number starting at 1. For each team in the test case (in the same order that they are given in the input), your program should output the name of the team on a single line. Then it should output a line with two integers t and n, where n is the number of uniforms needed for a given size t (1 ≤ t ≤ 50, 1 ≤ n), for all distinct sizes needed in the team. Sizes should be printed in ascending order.
Sample Input
3 12 LightningSalsa 1 PinkChiguiro 6 MightyPiranha 12
1 16 4 2 3 4 5
2 14 4 1 3 4 6
3 14 4 1 2 4 9
4 14 3 1 2 3
5 16 4 1 6 7 8
6 14 4 2 5 7 8
7 14 3 5 6 8
8 18 4 5 6 7 10
9 16 4 3 10 11 12 10 16 4 8 9 11 12 11 14 3 9 10 12
12 14 3 9 10 11 26 TamalSuperDragon 1 ArequipeNinjas 4
1 12 2 2 3
2 14 2 1 3
3 18 2 1 2
4 20 2 5 6
5 22 2 4 6
6 24 2 4 5
00
Sample Output
Case 1:
LightningSalsa
14 3
16 1
PinkChiguiro
14 2
16 1
18 1
MightyPiranha
14 2
16 2
Case 2:
TamalSuperDragon
3/3
12 1
14 1
18 1
ArequipeNinjas
20 1
22 1 24 1