P14807 [CCPC 2024 哈尔滨站] 欢迎加入线上会议!

题目描述

你想在 MeLink 上组织一次有 $n$ 位参会者的线上会议,参会者编号为 $1$ 到 $n$。对于这 $n$ 位参会者的每一位,都至少认识一位除了自己之外的参会者,认识关系是双向的。 会议的组织过程如下:首先由一个人创建会议并加入。随后,已经进入会议的成员可以拉一些自己认识但还没入会的参会者入会,直到所有 $n$ 位参会者都入会。但是有 $k$ 位参会者正忙着调试程序,这些人可以被拉进会议,但不会创建会议或拉他认识的人入会。 你希望确定是否有可能让所有 $n$ 位成员都入会。如果可行,请确定拉人入会的方案。

输入格式

第一行三个整数 $n, m, k$ ($2 \le n \le 2 \times 10^5$, $1 \le m \le \min\{5 \times 10^5, \frac{n(n-1)}{2}\}$, $0 \le k \le n$),分别表示参会者人数,互相认识的关系数和目前正忙的人数。 第二行 $k$ 个整数 $a_1, \ldots, a_k$ ($1 \le a_i \le n$),其中第 $i$ 个整数表示第 $a_i$ 位成员正忙。这些整数两两不同。如果 $k=0$,这一行将为空,但不会省略。 接下来的 $m$ 行中,每行两个整数 $p_i$ 和 $q_i$ ($1 \le p_i, q_i \le n$, $p_i \neq q_i$),表示 $p_i$ 和 $q_i$ 相互认识。认识关系是双向的。保证同一认识关系不会重复出现,且每个人都至少认识另一个人。

输出格式

如果无法组织有这 $n$ 位成员参加的会议,则在第一行输出 $\texttt{No}$。 如果可以,则在第一行输出 $\texttt{Yes}$。接下来,在第二行输出一个整数 $t$ ($1 \le t \le n$),表示组织该会议所需的步骤数。 接下来 $t$ 行,每行描述组织该会议的一步。在第 $j$ 行,首先输出一个整数 $x_j$ ($1 \leq x_j \leq n$)。如果 $j=1$,则 $x_j$ 表示创建会议的成员,否则,$x_j$ 必须是已经被拉入会议的一位成员。所有的 $x_j$ 应两两不同。接下来,输出一个整数 $y_j$ ($1 \leq y_j \leq n$),表示 $x_j$ 拉 $y_j$ 个成员入会。最后,输出 $y_j$ 个整数 $z_l$ ($1 \leq z_l \leq n$),表示被 $x_j$ 拉入会议的成员编号。$z_l$ 应当两两不同,并且整个过程中同一个人不能多次被拉入会。 你不必最小化 $t$,输出任意一种合法方案均可。