P14779 [COCI 2025/2026 #3] 宴会 / Domjenak

本题满分 $110$。

Malnar 先生正在为他的 $2N$ 位同事举办宴会，同事编号为 $1,2,\dots,2N$。同事们是两两成对来到宴会的。Malnar 先生观察到这群人传播信息时遵循一些奇怪规则： 第一，当且仅当两人是朋友，A 才愿意把信息告诉 B。保证一起到宴会的那一对同事互为朋友。 第二，每个人最多只愿意向一个人分享信息，并且对方必须尚未知道该信息。 第三，每个人尝试分享信息时，优先级最高的是与自己同来宴会的搭档。 换句话说：若 A 与 B 同来宴会，并且 A 知道而 B 不知道某信息，则 A 一定会把信息告诉 B。由于规则 2，A 不会再把该信息告诉其他人；而 B 之后会尝试把信息告诉另一位朋友，如此继续。 第四，这群人可以被划分为两个子集，使得任意一对朋友都不在同一子集。 Malnar 先生打算把故事讲给其中一位同事，并关心最多能有多少位同事听到故事。若最大人数为 $K$，他还希望你给出一个长度为 $K$ 的序列 $a_1,a_2,\ldots,a_K$，使得如果他把故事讲给 $a_1$，那么对所有 $i=1,2,\ldots,K-1$，同事 $a_i$ 都能把故事讲给 $a_{i+1}$（符合上述传播规则）。 在整理规则时，Malnar 先生记录下了所有“朋友关系”，但忘记了当初哪些同事是成对来到宴会的。幸运的是，这些信息可以被唯一恢复：也就是说，存在且仅存在一种把 $2N$ 位同事划分为 $N$ 对的方式，使得同一对里的两人是朋友。 请你帮助 Malnar 先生回答上述问题。

第一行包含两个整数 $N, M$（$1 \le N \le 5\cdot 10^5$，$N \le M \le 10^6$），分别表示参加宴会的同事“对数”与朋友关系条数。 接下来 $M$ 行，每行包含两个整数 $u_i, v_i$（$1 \le u_i, v_i \le 2N$），表示 $u_i$ 与 $v_i$ 是朋友。

第一行包含一个整数 $K$，表示最多能听到故事的人数。 第二行包含 $K$ 个整数，给出满足条件的序列。若有多种可能的答案，输出任意一种即可。

#### 【样例解释】 样例 #1 解释：参加宴会的同事配对为：$(1,2)$、$(3,4)$。 样例 #2 解释：参加宴会的同事配对为：$(1,6)$、$(2,3)$、$(4,5)$。可以证明不存在更长的可行序列。 例如序列 $(3,2,1,4,5)$，虽然相邻两人都是朋友，但 $1$ 从 $2$ 听到故事后无法把故事告诉 $4$，因为 $1$ 的宴会搭档 $6$ 仍不知道故事（规则 3 的优先级阻止了该传播）。 #### 【子任务】 | 子任务 | 分值 | 限制 | |:---:|:---:|:---:| | $1$ | $24$ | $N \le 10$ | | $2$ | $16$ | 每位同事最多与 $2$ 位同事是朋友 | | $3$ | $30$ | $N \le 2000$，$M \le 5000$ | | $4$ | $40$ | 无额外限制 |