Programming League 2004/05

One of the most popular types of computer multiplayer games in existence is the simple deathmatch shooter, in which it is the player's task to eliminate all other players on the gaming board. Usually, at the start of the game the players are distributed fairly randomly over the board, and run around in order to find and shoot opponents.

But there is a fair percentage of players (especially the younger ones) who enjoy the shooting most and give up the running altogether. To achieve this, at the start of the match all players are arranged very close to each other, and everyone opens fire in the very first second of the game. The gunfire continues until everyone within sight of everyone else is dead, and then the game ends, since no one feels like moving from their selected camping point.

Parents are often helpless when their children get addicted to this sort of entertainment, and don't know how to make them stop playing without causing a major quarrel. But Johnny's dad has developed the perfect method. He always says to his son: Sure, I'll let you play another round, but tell me please how long it'll take! And no, the answer only a minute or two is just not good enough.

At the start of the game, the players are positioned on the board and each player has a list of other players he is capable of eliminating (from his location). At the start of every second, each living player fires a round towards one of the opponents on his list (provided the list is not yet empty). Players who have been hit are eliminated from the game directly after the shots were fired. The situation continues until the lists of all surviving players are empty.

We are not asking you to give an exact answer the question posed by Johnny's dad, but only for an honest estimate. Given an arrangement of players on the board, try to find scenarios of shooting leading to the longest possible and the shortest possible game.

Input

The first line of input contains a single integer t, the number of test cases (t=100). t test cases follow. Each test case starts with a line containing integer n, denoting the number of players on the board (2<=n<=500). Each of the next n lines contains a list of integers: first, d_i the length of the i-th player's list, followed by the considered list of exactly d_i other players (numbered in input order from the range 1 to n).

Output

For the i-th test case output a line with the text case i Y or case i N, specifying whether you wish to solve the given case. Then in the former case print a description of the longest known game scenario, followed by a description of the shortest known game scenario. Each scenario starts with an integer t, the duration of the game measured in seconds (0<=t<=n-1). Each of the next t lines contains a list of integers, representing the identifiers of players eliminated by respective players in the given second (one integer for each player left alive and capable of hitting an enemy at the start of the second, ordered according to the input identifiers of the shooting players).

Score

The score awarded to your program is the total of scores for the test cases you chose to solve.

For each solved test case you will receive t_max / t_min-1 points, where t_max is the length of the first presented scenario, while t_min - the length of the second one.

Example

Input:
1
4
2 2 3
2 1 3
3 1 2 4
1 3

Output:
case 1 Y
2
3 3 4 3
2 1
1
2 1 4 3

Score:
2/1 - 1 = 1.00