P4957 [COCI 2017/2018 #6] Alkemija

在古代，当炼金术士们在寻找黄金时，世界上已知共有 N 种不同的物质，用 1 到 N 表示。经过多年的努力，寻找秘密配方，炼金术士们发现了一系列有趣的规律——炼金反应。在一种反应中，可以将物质集合 $\{X_1, X_2, \ldots, X_L\}$ 转化为另一种物质集合 $\{Y_1, Y_2, \ldots, Y_R\}$。例如，物质集合 $\{1, 4, 5\}$ 可能反应一次并生成新的物质集合 $\{2, 6\}$。 Joško 是一位现代炼金术士，他拥有 M 种不同的物质，用 $A_1, A_2, \ldots, A_M$ 表示。他拥有这些物质的无限量。Joško 想知道他可以使用古代炼金术士的反应列表创造出哪些物质，所以他请你帮助他解决这个问题。

输入的第一行包含两个整数 N 和 M ($1 \leq M \leq N \leq 100\,000$)，即题目中的数字。 输入的第二行包含 M 个整数 $A_i$ ($1 \leq A_i \leq N$)，表示 Joško 起初拥有的物质的标签。 输入的第三行包含整数 K ($1 \leq K \leq 100\,000$)，即已知反应的数量。 接下来的 $3 \cdot K$ 行包含反应列表。每个反应由以下 3 行描述： - 第一行包含整数 L 和 R ($1 \leq L, R \leq N$)。 - 第二行包含 L 个不同的整数 $X_i$ ($1 \leq X_i \leq N$)。 - 第三行包含 R 个不同的整数 $Y_i$ ($1 \leq Y_i \leq N$)。 - 这描述了物质集合 $\{X_1, X_2, \ldots, X_L\}$ 转化为物质集合 $\{Y_1, Y_2, \ldots, Y_R\}$ 的反应。 所有 L 值的总和不会超过 100\,000。 所有 R 值的总和不会超过 100\,000。

输出的第一行必须包含整数 X，即可以获得的物质数量。 输出的第二行必须包含 X 个不同的整数 $B_i$，按升序排列，表示可以获得的物质的标签。

在总分值的 60% 的测试用例中，将满足： - $N, K \leq 500$。 - 所有 L 值的总和和所有 R 值的总和不会超过 500。 **第一个测试用例的说明：** 有 2 个反应。 第一个反应将物质集合 $\{1, 2\}$ 转化为物质集合 $\{3\}$。 第二个反应将物质集合 $\{1, 3\}$ 转化为物质集合 $\{4\}$。 Joško 起初拥有物质集合 $\{1, 2\}$。 使用第一个反应，Joško 可以获得物质 3，之后他拥有物质集合 $\{1, 2, 3\}$。 之后，使用第二个反应，他还可以获得物质 4。 **第二个测试用例的说明：** Joško 起初拥有物质集合 $\{1, 4, 5\}$。 使用第二个反应，可以获得物质 6，之后可以应用第三个反应，得到物质 2。 第一个反应无法应用，因为 Joško 没有物质 3。 题面翻译由 ChatGPT-4o 提供。