问题陈述
如今,现代青少年使用 SNS 相互交流。
在一所高中,$N$ 学生正在使用名为 ICPC(国际编程竞赛社区)的 SNS。 这些$N$学生中的一些是这个SNS上的“朋友”,并且可以互相发送消息。 在这些$N$学生中,一年级$A$学生、二年级$B$学生和三年级$C$学生都是编程协会的成员。 注意,可能有一些学生不是编程协会的成员,所以$A+B+C$可以小于$N$。
学会内同年级会员之间关系良好。 这样,每个年级的SNS中都会有一个聊天群,同年级的社团成员可以通过群聊即时交流。 另一方面,任何不同年级之间的关系都不太好,没有整个协会和整个高中的聊天群。
为了在SNS上向所有社团成员广播消息,社团管理员想出了一个方法:管理员将消息告诉其中一名$N$学生,让他们通过聊天群和他们的朋友在SNS上传播消息。 (管理员本身没有SNS帐户。)由于同年级的成员可以通过该年级的聊天组广播该消息,因此我们可以假设,如果某个年级的其中一个成员收到该消息,则该年级的所有其他成员也会立即收到该消息。 因此,如果该消息被告知每个年级的至少一名成员,我们可以假设该消息在SNS上被广播给协会的所有成员。
因为朋友之间沟通比较麻烦,所以我们希望尽量减少朋友之间的沟通次数。 好友之间至少要进行多少次通信才能向所有协会成员广播消息? 为了实现最少的沟通,管理员应该首先向谁传达该消息?
输入
输入由单个测试用例组成。 测试用例的格式如下:
$N$ $A$ $B$ $C$
$a_1$ ... $a_A$
$b_1$ ... $b_B$
$c_1$ ... $c_C$
$M$
$x_1$ $y_1$
...
$x_M$ $y_M$
第一行包含四个整数 $N$、$A$、$B$ 和 $C$。 $N$ ($3 \leq N \leq 10{,}000$) 表示 SNS 中的学生人数,$A$、$B$ 和 $C$ ($1 \leq A, B, C \leq N$ 和 $A + B + C \leq N$) 分别表示一年级、二年级和三年级的会员人数。 SNS 上的每个学生都由一个介于 $1$ 和 $N$ 之间的唯一数字 ID 表示。 第二行包含$A$整数$a_1, \cdots, a_A$ ($1 \leq a_1, \cdots, a_A \leq N$),它们是一年级成员的ID。 第三行包含$B$整数$b_1, \cdots, b_B$ ($1 \leq b_1, \cdots, b_B \leq N$),它们是二年级成员的ID。 第四行包含$C$整数$c_1, \cdots, c_C$ ($1 \leq c_1, \cdots, c_C \leq N$),它们是三年级成员的ID。 您可以假设 $a_1, \cdots, a_A, b_1, \cdots, b_B, c_1, \cdots, c_C$ 是不同的。 第五行包含一个整数 $M$ ($2 \leq M \leq 500{,}000$)。 $M$表示在SNS中成为好友的学生对的数量。 接下来的$M$行中的第$i$行包含两个整数$x_i$和$y_i$($1 \leq x_i, y_i \leq N$),这意味着ID为$x_i$的学生和ID为$y_i$的学生是SNS中的好友。 您可以假设 $x_i \neq y_i$ ($1 \leq i \leq M$) 和 ($x_i \neq x_j$ 或 $y_i \neq y_j$) 和 ($x_i \neq y_j$ 或 $y_i \neq x_j$) 如果 $i \neq j$ ($1 \leq i, j \leq M$)。 您还可以假设任何学生都可以通过朋友和群聊将消息传递给 SNS 中的任何学生。
输出
输出在所有社团成员之间广播消息的好友之间(不包括群聊)的最少通讯次数,以及管理员为了达到最少通讯次数而应该告诉的学生的ID,用一个空格分隔。 如果有多个学生满足上述约束条件,则输出这些学生的最小ID。
示例输入 1
4 2 1 1 1 2 3 4 3 1 2 2 4 3 4
样本输入 1 的输出
2 1
示例输入 2
4 1 1 1 2 3 4 4 1 2 1 3 1 4 2 4
样本输入 2 的输出
3 1
示例输入 3
8 1 2 2 5 4 6 3 8 7 1 2 2 3 3 4 5 6 6 7 7 8 2 6
样本输入 3 的输出
2 3