Description

在古代，当炼金术士们在寻找黄金时，世界上已知共有 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 想知道他可以使用古代炼金术士的反应列表创造出哪些物质，所以他请你帮助他解决这个问题。

Input Format

输入的第一行包含两个整数 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。

Output Format

输出的第一行必须包含整数 X，即可以获得的物质数量。

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

4 2
1 2
2
2 1
1 2
3
2 1
1 3
4

4
1 2 3 4

6 3
1 4 5
3
3 2
2 3 4
1 6
1 3
4
1 5 6
1 1
6
2

5
1 2 4 5 6

Hint

在总分值的 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 提供。