题目描述
In ancient times, when alchemists were searching for gold, the world was familiar with a total of N distinct substances, denoted with 1 to N. During many years of hard work, searching for the secret formula, alchemists discovered a series of interesting regularities - alchemical reactions . In one reaction, it’s possible to transform substance set { $X_1$,$X_2$, …, $X_L$} to another substance set {$Y_1$, $Y_2$, …, $Y_R$}. For example, the substance set {1, 4, 5} might react once and create the new substance set {2, 6}.
Joško is a modern alchemist and has M distinct substances denoted with $A_1$, $A_2$, …, $A_M$. He has an unlimited quantity of each substance from that set. Joško wants to know which substances he can create using a list of reactions of ancient alchemists, so he’s asking you to help him solve this problem.
输入格式
The first line of input contains two integers N and M (1 ≤ M ≤ N ≤ 100 000), the numbers from the task.
The second line of input contains M integers $A_i$ (1 ≤ $A_i$ ≤ N), labels of the substances Joško has in the beginning.
The third line of input contains the integer K (1 ≤ K ≤ 100 000), the number of known reactions.
The following 3·K lines contain a list of reactions. Each reaction is described with 3 lines in the following way:
- The first line contains the integers L and R (1 ≤ L, R ≤ N).
- The second line contains L distinct integers $X_i$ (1 ≤ $X_i$ ≤ N).
- The third line contains R distinct integers $Y_i$ (1 ≤ $Y_i$ ≤ N).
- This describes the reaction with which the substance set {$X_1$, $X_2$, …, $X_L$} transforms into substance set {$Y_1$, $Y_2$, …, $Y_R$}.
The sum of all L values won’t exceed 100 000.
The sum of all R values won’t exceed 100 000.
输出格式
The first line of output must contain the integer X, the number of obtainable substances.
The second line of output must contain X distinct integers $B_i$, sorted ascendingly, that represent the labels of the obtainable substances.
题目描述
在古代，当炼金术士寻找黄金时，全世界一共熟悉N种不同的物质，用1到N进行表示。在经过多年的努力之后，炼金术士们发现了一个有趣的规律。在一个反应中，可以将物质集{X1,X2,…,XL}转化为另一个物质集{Y1,Y2,…,YR}。例如，物质集{1,4,5}可能会发生反应一次转化为物质集{2,6}.
Josko是一位现代炼金术士，他有M种不同的物质，表示为A1,A2,…AM，每种物质有无限量这么多。Josko想知道，他可以通过古代炼金术士的反应清单反应后，他能够拥有哪些物质？
输入格式
第一行输入两个数字N（1≤N≤100000），M（1≤M≤100000），表示古代炼金术士所熟悉的N种物质以及Josko所拥有的物质种类。
第二行输入M个数字Ai，表示Josko所拥有哪些种物质。
第三行输入一个数字K（1≤K≤100000），表示古代炼金术士所知道的反应数。
接下来输入3*K行，每三行中的第一行输入两个数字L和R（1≤L,R≤N），表示反应前和反应后的物质种类数。第二行输入L个数字Xi，表示反应前物质的种类。第三行输入R个数字Yi表示反应后的种类。
题目保证L和R的总和分别不超过100000.
输出格式
第一行输出一个数字X，表示Josko最终能得到多少种物质。
第二行输出X个数，每个数表示Josko反应后得到的物质种类。
样例 #1
样例输入 #1
4 2
1 2
2
2 1
1 2
3
2 1
1 3
4样例输出 #1
4
1 2 3 4样例 #2
样例输入 #2
6 3
1 4 5
3
3 2
2 3 4
1 6
1 3
4
1 5 6
1 1
6
2样例输出 #2
5
1 2 4 5 6提示
In test cases worth 60% of total points, it will hold:
- N, K ≤ 500.
- The sum of all L values and the sum of all R values won’t exceed 500.
Clarification of the first test case:
有2个反应。
第一个反应将物质集 {1, 2} 转化为物质集 {3}。
第二个反应将物质组 {1, 3} 转化为物质组 {4}。
Joško 最初有来自集合 {1, 2} 的物质。
使用第一个反应，Joško 可以得到物质 3，之后他得到集合 {1,2,3} 中的物质。
之后，利用第二个反应，他也可以得到物质4。
Clarification of the second test case:
Joško 最初有来自集合 {1, 4, 5} 的物质。
使用第二个反应，可以得到物质 6，之后可以应用第三个反应，得到物质 2。
第一个反应是不可能应用的，因为 Joško 没有物质 3。