Tommy discovers the relics of ~m~ messages ~[X_1, X_2, \dots, X_m]~ corresponding to ~n~ clowns participating in a forum thread. A message ~X_i~ can be described by three strings ~X_{i\ 1}, X_{i\ 2}, X_{i\ 3}~. Tommy will reorder the ~m~ messages into some sequence ~[Y_1, Y_2, \dots, Y_m]~. A message ~Y_i~ is good if and only if either

• ~i \ne m~, ~Y_{i\ 3} = \texttt{`loushang'}~ and ~Y_{i\ 2} = Y_{i+1\ 1}~
• ~i \ne 1~, ~Y_{i\ 3} = \texttt{`louxia'}~ and ~Y_{i\ 2} = Y_{i-1\ 1}~

Find any ordering of the ~m~ given messages that maximizes the number of good messages.

Let ~S = \{X_{i\ 1} : 1 \le i \le m\}~. The test data guarantees that ~|S| = n~ and that for any ~X_{i\ 1}~, there exists ~j~ such that ~X_{j\ 1} = X_{i\ 1}~ and ~X_{j\ 3} \notin \{\texttt{`loushang'}, \texttt{`louxia'}\}~.

Constraints

The input consists of ~T \le 100~ individual test cases.

For each test case, ~1 \le n \le m \le 77\,777~.

Over all test cases, ~\sum m \le 2.5 \times 10^5~.

The length of any token of input will not exceed ~12~ ASCII characters.

~50\%~ of points will be granted for finding the maximum number of good messages but failing to find a valid ordering.

~T \le~	~M \le~	~\sum M \le~	Test	Prop. A	Prop. B	Prop. C
~5~	~10~	~50~	1	/	/	/
~10~	~16~	~160~	2	/	/	/
~30~	~2\,222~	~15\,000~	3, 4	Y	Y	Y
~30~	~2\,222~	~15\,000~	5, 6	Y	/	Y
~30~	~2\,222~	~15\,000~	7, 8, 9	/	Y	Y
~30~	~2\,222~	~15\,000~	10, 11	/	/	Y
~30~	~2\,222~	~15\,000~	12, 13	/	/	/
~100~	~77\,777~	~2.5 \times 10^5~	14, 15	Y	Y	Y
~100~	~77\,777~	~2.5 \times 10^5~	16	Y	/	Y
~100~	~77\,777~	~2.5 \times 10^5~	17, 18, 19	/	Y	Y
~100~	~77\,777~	~2.5 \times 10^5~	20, 21, 22	/	/	Y
~100~	~77\,777~	~2.5 \times 10^5~	23, 24, 25	/	/	/

Property A: There is no ~i~ where ~X_{i\ 3} = \texttt{`loushang'}~ and ~X_{i\ 2} \in S~.

Property B: There exists an ordering such that all ~i~ where ~X_{i\ 3} \in \{\texttt{`loushang'}, \texttt{`louxia'}\}~ and ~X_{i\ 2} \in S~, are good messages.

Property C: There exists no pair ~1 \le i, j \le m~ where ~X_{i\ 1} = X_{j\ 2}~, ~X_{i\ 2} = X_{j\ 1}~, ~X_{i\ 3} = \texttt{`loushang'}~, and ~X_{j\ 3} = \texttt{`louxia'}~.

Input Specification

The first line contains a positive integer ~T~, the number of test cases. For each test case:

The first line contains two positive integers ~n~ and ~m~, the number of clowns and the number of messages, respectively.

The following ~n~ lines contain the names of the clowns.

The following ~m~ lines contain three strings ~X_{i\ 1}~, ~X_{i\ 2}~, and ~X_{i\ 3}~, describing message ~X_i~.

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 ~m~ distinct integers ~a_1, a_2, \dots, a_m~ from ~1~ to ~m~, corresponding to an ordering of the messages, i.e. ~Y_i = X_{a_i}~.

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

Attachments