Tommy discovers the relics of messages corresponding to clowns participating in a forum thread. A message can be described by three strings . Tommy will reorder the messages into some sequence . A message is good if and only if either
- , and
- , and
Find any ordering of the given messages that maximizes the number of good messages.
Let . The test data guarantees that and that for any , there exists such that and .
Constraints
The input consists of individual test cases.
For each test case, .
Over all test cases, .
The length of any token of input will not exceed ASCII characters.
of points will be granted for finding the maximum number of good messages but failing to find a valid ordering.
Test | Prop. A | Prop. B | Prop. C | |||
---|---|---|---|---|---|---|
1 | / | / | / | |||
2 | / | / | / | |||
3, 4 | Y | Y | Y | |||
5, 6 | Y | / | Y | |||
7, 8, 9 | / | Y | Y | |||
10, 11 | / | / | Y | |||
12, 13 | / | / | / | |||
14, 15 | Y | Y | Y | |||
16 | Y | / | Y | |||
17, 18, 19 | / | Y | Y | |||
20, 21, 22 | / | / | Y | |||
23, 24, 25 | / | / | / |
Property A: There is no where and .
Property B: There exists an ordering such that all where and , are good messages.
Property C: There exists no pair where , , , and .
Input Specification
The first line contains a positive integer , the number of test cases. For each test case:
The first line contains two positive integers and , the number of clowns and the number of messages, respectively.
The following lines contain the names of the clowns.
The following lines contain three strings , , and , describing message .
Output Specification
For each test case:
On the first line output an integer, corresponding to the maximum number of good messages.
On the second line output distinct integers from to , corresponding to an ordering of the messages, i.e. .
Sample Input
2
4 15
builtin_clz
builtin_ctz
jinkela
OrzTourist
builtin_clz MengXin QiuZhu
builtin_ctz builtin_clz louxia
jinkela builtin_ctz louxia
builtin_ctz builtin_clz loushang
builtin_clz BieMoZheng YaoXueShu
OrzTourist builtin_clz louxia
OrzTourist OrzTourist louxia
builtin_clz Iam Angry!
builtin_clz builtin_clz loushang
builtin_clz builtin_clz louxia
builtin_clz builtin_clz loushang
builtin_clz builtin_clz louxia
builtin_ctz Xue Shu
jinkela Xue Shu
OrzTourist Xue Shu
1 9
builtin_clz
builtin_clz builtin_clz loushang
builtin_clz builtin_clz loushang
builtin_clz builtin_clz louxia
builtin_clz builtin_clz Loushang
builtin_clz builtin_clz LOUSHANG
builtin_clz Builtin_clz loushang
builtin_clz loushang louxia
builtin_clz builtin_clz builtin_clz
builtin_clz loushang builtin_clz
Sample Output
9
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
3
8 1 2 7 9 3 6 4 5
Comments