【统一省选2022】学术社区 - 题目

题目背景

小 I 的温馨提示：在题目描述中有形式化的题面，你可以选择跳过题目背景。同时请仔细将本题的除题目背景以外的所有内容进行完整阅读后再进行做题。

小 I 是一个喜欢 OI 的选手，不过，与其说小 I 喜欢 OI，不如说小 I 喜欢的是他最经常使用的 OJ——FCCOJ——上的趣味功能：学术社区。虽说名字叫学术社区，但小 I 和网友们能够谈论的东西远不止学术。每天学术社区里总会出现不少吸引小 I 注意的帖子。今天小 I 在学术社区冲浪时发现了一个这样的帖子：

builtin_clz：萌新求助，学术社区这题，本机 AC 提交 RE

builtin_ctz：builtin_clz 楼下

jinkela：builtin_ctz 楼下

builtin_ctz：builtin_clz 楼上

builtin_clz：能不能别魔怔了，大家正经回答问题

OrzTourist：builtin_clz 楼下

OrzTourist：OrzTourist 楼下

builtin_clz：怎么没有人回答问题，我生气了！

builtin_clz：builtin_clz 楼上

builtin_clz：builtin_clz 楼下

builtin_clz：builtin_clz 楼上

builtin_clz：builtin_clz 楼下

……

虽然这个名叫 builtin_clz 的网友因为没有人回答他的学术问题被激怒了，但这个有趣的发言方式让小 I 乐呵了许久，这说明人类的悲欢并不相通。不过当小 I 刷新界面想要往下浏览大家的回复时，却发现学术社区的管理员因为这个帖子过于灌水把它删除了。

为了恢复这个有趣的帖子，小 I 对着网页缓存倒腾了许久，还原出了这个帖子的每条消息。然而因为神秘原因，消息的顺序被打乱了，且缓存中没有每条消息发送的时间，因而小 I 没有办法还原原始帖子中消息的顺序。

秉承「遇到困难睡大觉」精神的小 I 决定随便给帖子里的消息排个顺序，不过深受「XXX 楼上」「XXX 楼下」这种发言形式吸引的小 I 还是希望重排之后有尽可能多的这种形式的消息的表达是符合帖子的实际情况的。然而小 I 是一个只会水社区不会做题的 OI 选手，所以小 I 求助于你。

当然了，小 I 知道直接将帖子中的原始信息丢给你对你来说是不方便的，所以他对信息进行了一些规范化处理，详见题目描述中的形式化题意。同时由于学术社区的特殊规定，帖子中的消息满足一定特殊限制，详见题目描述最后。

题目描述

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

小 I 正在整理学术社区中的一个帖子。帖子中共有 $N$ 个网友发过消息，他们的网名分别为 $n_{1}, n_{2}, \dots, 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}, \dots, 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}, \dots, a_{M}$ 中的第 $i (1 \leq i \leq M)$ 条消息 $(s_{a_{i}, 1}, s_{a_{i}, 2}, s_{a_{i}, 3})$ ，如下定义其是否是符合实际情况的： - 若这条消息是楼下型消息，则这条消息是符合实际情况的当且仅当 $i \neq 1$ 且 $s_{a_{i - 1}, 1} = s_{a_{i}, 2}$ ，即上一条消息存在且它的发出者与这条消息提到的网友一致。 - 若这条消息是楼上型消息，则这条消息是符合实际情况的当且仅当 $i \neq M$ 且 $s_{a_{i + 1}, 1} = s_{a_{i}, 2}$ ，即下一条消息存在且它的发出者与这条消息提到的网友一致。 - 若这条消息是学术消息，则无论如何这条消息一定不是符合实际情况的，这是因为小 I 只想灌水不想学术。

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

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

输入格式

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

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

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

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

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

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

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

输出格式

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

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

第二行输出 $M$ 个整数 $a_{1}, a_{2}, \dots, a_{M}$ ，表示符合实际情况的消息最多的重排方案。若有多种合法的重排方案，输出任意一个即可。

样例一

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

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

explanation

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

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

样例二、三、四

见附件下载。

数据范围与提示

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

对于所有测试点， $1 \leq T \leq 10^{2}, 1 \leq N \leq M \leq 77, 777, 1 \leq \sum M \leq 2.5 \times 10^{5}$ 。

$T \leq$	$M \leq$	$\sum M \leq$	测试点编号	特殊性质 A	特殊性质 B	特殊性质 C
$5$	$10$	$50$	$1$	无	无	无
$10$	$16$	$160$	$2$	无	无	无
$30$	$2, 222$	$15, 000$	$3, 4$	有	有	有
$30$	$2, 222$	$15, 000$	$5, 6$	有	无	有
$30$	$2, 222$	$15, 000$	$7, 8, 9$	无	有	有
$30$	$2, 222$	$15, 000$	$10, 11$	无	无	有
$30$	$2, 222$	$15, 000$	$12, 13$	无	无	无
$10^{2}$	$77, 777$	$2.5 \times 10^{5}$	$14, 15$	有	有	有
$10^{2}$	$77, 777$	$2.5 \times 10^{5}$	$16$	有	无	有
$10^{2}$	$77, 777$	$2.5 \times 10^{5}$	$17, 18, 19$	无	有	有
$10^{2}$	$77, 777$	$2.5 \times 10^{5}$	$20, 21, 22$	无	无	有
$10^{2}$	$77, 777$	$2.5 \times 10^{5}$	$23, 24, 25$	无	无	无

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

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

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

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

评分方式

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

提示

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

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

时间限制： $1.5 s 3 s$

空间限制： $512 MB$

Universal Online Judge

UOJ

#736. 【统一省选2022】学术社区