Description
A pleasant headache that parents have every year is preparing Christmas gifts for their children. Because each child envies each other having seen what others received, the parents have to prepare gifts so that no child should envy any other child.
Before a husband and wife go for Christmas shopping, they announce to their children a fixed set of gift candidates and declare that each child will receive a subset of the candidates. The children then respond to the parents with conditions for them to be happy. Each child's condition is relatively defined in terms of the gifts that other siblings would have. The goal of the parents is to satisfy all their children's conditions with the smallest such gift set for each child.
Each child's condition is always expressed as a conjunction:
I need at least (a1 and a2 and ... and an)
where each ai is either
[type 1] a constant subset of the gift candidates, or
[type 2] one sibling's name (meaning his/her gifts), or
[type 3] "common-things-of" two ai of type 1 or 2 (meaning the gifts that are common among the two), or
[type 4] one sibling's name followed by "except-for" a constant subset of the gift candidates (meaning the sibling's gifts excluding those in the constant subset).
For example, for three children {X, Y, Z} and for three candidates {a, b, c} for gifts, let the condition for each child be:
X needs at least ({a, b} and common-things-of (Y, Z))
Y needs at least (common-things-of (Z, {b, c}))
Z needs at least ({a} and (X except-for {c}))
Then the smallest gifts for each child that satisfy his/her condition are {a, b} for X, {b} for Y, and {a, b} for Z.
Input
The input consists of T test cases. The number of test cases (T) is given in the first line of the input file. Gift candidates are numbered from 1 to n ( 1<=n<=1000 ). Children are numbered from 1 to m (1<=m<=100). The input is a sequence of non-empty lines:
The first line has the number (T) of test cases. The sequence of test cases is from the second line.
The first line of each test case has two integers, the number (n) of gift candidates followed by the number (m) of children.
The next lines show the sequence of children's conditions in the order of child 1's, child 2's,..., child m's. Each child's condition is expressed as follows:
----The first line has two integers, the child's identification and the number of ai's
----From the second line, one line represents one part (the ai) of the child's condition. Each line for starts with its type:
"-1" for type 1, "-2" for type 2, "-3" for type 3, and "-4" for type 4.
[type 1] "-1" is followed by a number k and a sequence of integers for the gift elements. The k is the number of integers in the sequence. It represents a constant set of gift candidates. For example,
-1 2 1 2
represents a set {1, 2} of gifts.
[type 2] "-2" is followed by a single integer for a sibling's identification. For example,
-2 2
represents sibling 2's gifts.
[type 3] "-3" is followed by a sequence of two formats of type 1 or 2. For example,
-3 -2 3 -1 2 2 3
represents the common-things-of sibling 3's gifts and set {2, 3}. As another example,
-3 -2 2 -2 3
represents the common-things-of sibling 2's and 3's gifts.
[type 4] "-4" is followed by type 2 followed by type 1. For example,
-4 -2 1 -1 1 3
represents sibling 1's gifts except-for {3}.
Output
The output is the sequence of solutions for the given test cases. The solutions are printed in the order of the test cases. Each solution is the sequence of lines, one line per child, in the increasing order of children's identification numbers. Each line starts with the child's identification number followed by his/her gift identification numbers in the increasing order. For an empty gift, only the child number is printed.
Sample Input
3
2 2
1 1
-1 1 1
2 1
-4 -2 1 -1 1 1
1 1
1 1
-3 -1 1 1 -1 1 1
3 3
1 2
-1 2 1 2
-3 -2 2 -2 3
2 1
-3 -2 3 -1 2 2 3
3 2
-1 1 1
-4 -2 1 -1 1 3
Sample Output
1 1
2
1 1
1 1 2
2 2
3 1 2
