Description

Little I is a fan of OI. However, rather than saying Little I likes OI, it is more accurate to say that Little I likes the interesting feature on the OJ he uses most frequently—FCCOJ—called the "Academic Community." Although it is named the Academic Community, the topics Little I and other users discuss go far beyond academics. Every day, there are many posts in the Academic Community that catch Little I's attention. Today, while surfing the community, Little I found a post like this:

builtin_clz: Newbie asking for help, this problem in the Academic Community, AC locally but RE on submission. builtin_ctz: builtin_clz below. jinkela: builtin_ctz below. builtin_ctz: builtin_clz above. builtin_clz: Can you guys stop being weird, please answer the question seriously. OrzTourist: builtin_clz below. OrzTourist: OrzTourist below. builtin_clz: Why is no one answering the question, I'm angry! builtin_clz: builtin_clz above. builtin_clz: builtin_clz below. builtin_clz: builtin_clz above. builtin_clz: builtin_clz below. ……

Although the user named builtin_clz was angered because no one answered his academic question, this interesting way of posting made Little I laugh for a long time, which goes to show that human joys and sorrows are not necessarily connected. However, when Little I refreshed the page to browse the replies, he found that the administrators of the Academic Community had deleted the post for being too much "spam."

To recover this interesting post, Little I spent a long time digging through web caches and restored every message in the post. However, for mysterious reasons, the order of the messages was scrambled, and the cache did not contain the time each message was sent, so Little I had no way to restore the original order of the messages in the post.

Adhering to the spirit of "sleeping when encountering difficulties," Little I decided to just arrange the messages in the post in some order. However, being fascinated by the "XXX above" and "XXX below" style of posting, Little I still hopes that after reordering, as many messages as possible will express a situation that is consistent with the actual post. Since Little I is an OI contestant who only knows how to spam in the community and cannot solve problems, he is asking you for help.

All string comparison operations involved below are case-sensitive; for example, loushang, Loushang, and LOUSHANG are distinct strings.

Little I is organizing a post in the Academic Community. There are $N$ users who have posted messages, and their usernames are $n_1, n_2, \dots, n_N$. There are a total of $M$ messages in the post. For the $i$-th message, we describe it with a triple of strings $(s_{i,1}, s_{i,2}, s_{i,3})$, where $s_{i,1}$ represents the username of the sender, and $s_{i,2}$ and $s_{i,3}$ describe the content of the message.

For the $i$-th message, we define whether it belongs to a "below-type message," "above-type message," or "academic message" as follows: If the string $s_{i,3}$ is louxia and $s_{i,2}$ is exactly the same as one of the given usernames (note that $s_{i,2} = s_{i,1}$ is allowed), then this message is called a below-type message, and $s_{i,2}$ corresponds to the user mentioned in this message. If the string $s_{i,3}$ is loushang and $s_{i,2}$ is exactly the same as one of the given usernames (note that $s_{i,2} = s_{i,1}$ is allowed), then this message is called an above-type message, and $s_{i,2}$ corresponds to the user mentioned in this message. If neither of the above conditions is met, then this message is called an *academic message.

A reordering scheme for all messages is defined as a permutation $a_1, a_2, a_3, \dots, a_M$ of $1$ to $M$, where the first message is $(s_{a_1,1}, s_{a_1,2}, s_{a_1,3})$, the second message is $(s_{a_2,1}, s_{a_2,2}, s_{a_2,3})$, and so on.

For the $i$-th ($1 \le i \le M$) message $(s_{a_i,1}, s_{a_i,2}, s_{a_i,3})$ in a reordering scheme $a_1, a_2, \dots, a_M$, we define whether it is consistent with the actual situation as follows: If this message is a below-type message, it is consistent with the actual situation if and only if $i \neq 1$ and $s_{a_{i-1},1} = s_{a_i,2}$, meaning the previous message exists and its sender is the same as the user mentioned in this message. If this message is an above-type message, it is consistent with the actual situation if and only if $i \neq M$ and $s_{a_{i+1},1} = s_{a_i,2}$, meaning the next message exists and its sender is the same as the user mentioned in this message. * If this message is an academic message, it is never consistent with the actual situation, because Little I only wants to spam and not do academics.

Under the above definitions, Little I wants to find a reordering scheme that maximizes the number of messages consistent with the actual situation. You need to help him find this scheme and the number of messages consistent with the actual situation in this scheme.

For your convenience, Little I also told you a special constraint on the messages in the post: because the Academic Community bans people who only spam and do not contribute academically, every person who has posted in the post must have posted at least one academic message.

Input

Read data from the file community.in.

This problem contains multiple test cases. The first line contains an integer $T$ representing the number of test cases. Then $T$ test cases follow.

For each test case, the first line contains two integers $N$ and $M$, representing the number of users who have posted and the number of messages in the post, respectively.

The next $N$ lines each contain a string $n$, representing the username of a user who has posted in the post. It is guaranteed that the $N$ usernames in each test case are distinct.

The next $M$ lines each contain three strings $s_1, s_2, s_3$ describing a message, separated by spaces, where $s_1$ is guaranteed to be equal to one of the usernames provided in the input.

All strings in the input consist only of uppercase and lowercase English letters, underscores (_), question marks (?), exclamation marks (!), and periods (.), and their length does not exceed 12.

For each test case, it is guaranteed that all $N$ users have posted at least one message, and at least one academic message.

Multiple messages with identical content may exist in the same test case; in this case, they should be treated as multiple distinct messages.

Output

Output to the file community.out.

For each test case, output two lines. The first line outputs a non-negative integer representing the maximum number of messages consistent with the actual situation among all reordering schemes. The second line outputs $M$ integers $a_1, a_2, \dots, a_M$, representing the reordering scheme with the maximum number of consistent messages. If there are multiple valid reordering schemes, output any one of them.

Constraints

Let $\sum M$ be the sum of $M$ over all test cases in a single test point. For all test points, $1 \le T \le 10^2$, $1 \le N \le M \le 77,777$, $1 \le \sum M \le 2.5 \times 10^5$.

Note: For readability, the test case ID is in the fourth column of the table.

Special Property A: No above-type messages. Note: This does not mean $s_3$ is not equal to loushang. Special Property B: For each test case, there exists a reordering scheme such that every above-type message and below-type message is consistent with the actual situation. Special Property C: For each test case, if there is a message $s_1 \ s_2 \ \text{loushang}$, where $s_1, s_2$ are arbitrary strings, then there is definitely no message $s_2 \ s_1 \ \text{louxia}$ in that test case.

Note

If you only wish to obtain 50% of the score, you must also ensure that you output a permutation of $1$ to $M$ on the second line for each test case; otherwise, the actual score may deviate from the expected score.

Because this may be important to you, Little I emphasizes again: because the Academic Community bans people who only spam and do not contribute academically, in the post provided by Little I, every person who has posted in the post must have posted at least one academic message.

The input size for this problem is large; please use a fast input method.