Description

以下涉及的所有字符串判等操作都对大小写敏感，例如 1oushang、Loushang、LOUSHANG 是互不相同的字符串。

小 I 正在整理学术社区中的一个帖子。帖子中一共有 $N$ 个网友发过消息，他们的网名分别为 $n_1, n_2, \ldots, n_N$。帖子中总共有 $M$ 条消息，对于第 $i$ 条消息，我们用三个字符串 $s_{i,1}, s_{i,2}, s_{i,3}$ 构成的三元组描述它，其中 $s_{i,1}$ 表示这条消息发出者的网名，而 $s_{i,2}$ 和 $s_{i,3}$ 描述这条消息的内容。

对于第 $i$ 条消息，我们通过如下方式定义其属于楼下型消息、楼上型消息、学术型消息中的哪一种：

• 若字符串 $s_{i, 3}$ 为 louxia，且 $s_{i, 2}$ 恰好与给出的某个网名相同（注意 $s_{i,2} = s_{i,1}$ 是允许的），则称这条消息是楼下型消息，$s_{i,2}$ 对应这条消息提到的网友；
• 若字符串 $s_{i,3}$ 为 loushang，且 $s_{i,2}$ 恰好与给出的某个网名相同（注意 $s_{i,2} = s_{i,1}$ 是允许的），则称这条消息是楼上型消息，$s_{i,2}$ 对应这条消息提到的网友；
• 若以上两个条件都不满足，则称这条消息是学术消息。

定义一个对所有消息的重排方案为一个 $1$ 到 $M$ 的排列 $a_1, a_2, a_3, \ldots, a_M$，表示第一条消息是 $(s_{a_1,1}, s_{a_1,2}, s_{a_1,3})$，第二条消息是 $(s_{a_2,1}, s_{a_2,2}, s_{a_2,3})$，依此类推。

对于一个重排方案 $a_1, a_2, a_3, \ldots, a_M$ 中的第 $i$（$1 \le i \le M$）条消息 $(s_{a_i,1}, s_{a_i,2}, s_{a_i,3})$，如下定义其是否是符合实际情况的：

• 若这条消息是楼下型消息，则这条消息是符合实际情况的当且仅当 $i \ne 1$ 且 $s_{a_{i - 1}, 1} = s_{a_i, 2}$，即上一条消息存在且它的发出者与这条消息提到的网友一致。
• 若这条消息是楼上型消息，则这条消息是符合实际情况的当且仅当 $i \ne M$ 且 $s_{a_{i + 1}, 1} = s_{a_i, 2}$，即下一条消息存在且它的发出者与这条消息提到的网友一致。
• 若这条消息是学术消息，则无论如何这条消息一定不是符合实际情况的，这是因为小 I 只想灌水不想学术。

在以上定义下，小 I 希望找到一个重排方案，使得该重排方案中符合实际情况的消息数量最多。你需要帮他找到这个方案以及这个方案中符合实际情况的消息数量。

为了方便你的解题，小 I 还告诉了你帖子中消息的一个特殊限制：因为学术社区会禁言在社区中只灌水不学术的人，所以在小 I 给出的帖子里，每一个在帖子中发过言的人都一定会在帖子中发出至少一条学术消息。

Input Format

本题有多组测试数据。第一行一个整数 $T$ 表示测试数据组数，接下来分别输入 $T$ 组数据。

对于每组测试数据，第一行两个整数 $N, M$ 分别表示帖子中发过消息的网友数量以及帖子的消息数量。

接下来 $N$ 行每行一个字符串 $n$ 表示在帖子中发过消息的一个网友的网名。保证每个测试数据中输入的 $N$ 个网友的网名两两不同。

接下来 $M$ 行每行三个字符串 $s_1, s_2, s_3$ 描述一条消息，相邻的字符串之间用一个空格分隔，其中 $s_1$ 一定与输入中某个网友的网名相等。

输入的所有字符串仅由大小写英文字母、下划线（_）、英文问号（?）、英文感叹号（!）和英文句号（.）构成，且长度不超过 $12$。

对于每组测试数据，保证输入的 $N$ 个网名都发出过至少一条消息，且至少发出过一条学术消息。

同一组测试数据中可能存在多条消息内容完全一致，此时应将他们视为多条消息。

Output Format

对于每组测试数据输出两行。

第一行输出一个非负整数表示所有重排方案中最大的符合实际情况的消息数量。

第二行输出 $M$ 个整数 $a_1, a_2, \ldots, a_m$，表示符合实际情况的消息最多的重排方案。

若有多种合法的重排方案，输出任意一个即可。

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

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

见附件中的 community/community2.in

见附件中的 community/community2.ans

Hint

【样例解释 #1】

第一个测试数据与题目背景中给出的例子基本一致，而不同的点在于：为了满足每个人至少发出一条学术消息的要求，在该组数据输入的最后有几条额外的学术消息。

第二个测试数据中，输入的前两条消息是楼上型消息，第三条消息是楼下型消息，其他消息是学术消息。

【样例 #3】

见附件中的 community/community3.in 与 community/community3.ans。

该组样例满足数据范围中的特殊性质 A、特殊性质 B、特殊性质 C。

【样例 #4】

见附件中的 community/community4.in 与 community/community4.ans。

该组样例满足数据范围中的特殊性质 C。

【数据范围】

设 $\sum M$ 为单个测试点中所有测试数据的 $M$ 的和。

对于所有测试点，$1 \le T \le 100$，$1 \le N \le M \le 77777$，$1 \le \sum M \le 2.5 \times {10}^5$。

$T \le$	$M \le$	$\sum M \le$	测试点编号	特殊性质 A	特殊性质 B	特殊性质 C
$5$	$10$	$50$	$1$	无
$10$	$16$	$160$	$2$
$30$	$2222$	$15000$	$3 \sim 4$	有	有	有
			$5 \sim 6$		无
			$7 \sim 9$	无	有
			$10 \sim 11$		无
			$12 \sim 13$			无
$100$	$77777$	$2.5 \times {10}^5$	$14 \sim 15$	有	有	有
			$16$		无
			$17 \sim 19$	无	有
			$20 \sim 22$		无
			$23 \sim 25$			无

注意：为了阅读方便，测试点编号在表格中的第四列。

特殊性质 A：没有楼上型消息。注意：这不意味着 $\bm{s_3}$ 不等于 loushang。

特殊性质 B：对于每组测试数据，存在一个重排方案，使得每一条楼上型消息和楼下型消息都是符合实际情况的。

特殊性质 C：对于每组测试数据，若存在一条消息是 $s_1$ $s_2$ loushang，其中 $s_1, s_2$ 为任意字符串，则该组数据中一定不存在一条消息是 $s_2$ $s_1$ louxia。

【评分方式】

若一个测试点内所有测试数据的符合实际情况的消息数量都正确，你将获得该测试点 $50 \%$ 的分数；在此基础上，若一个测试点内所有测试数据的重排方案都正确，你将获得该测试点的所有分数。需要注意的是，如果你只希望获得 $\bm{50 \%}$ 的分数，你也要保证在每组测试数据的第二行输出一个 $\bm{1}$ 到 $\bm{M}$ 的排列，否则实际分数与期望分数可能出现偏差。

【提示】

因为这对你可能很重要，所以小 I 再一次强调：因为学术社区会禁言在社区中只灌水不学术的人，所以在小 I 给出的帖子里，每一个在帖子中发过言的人都一定会在帖子中发出至少一条学术消息。

本题输入规模较大，请使用较为快速的输入方式。