CF243B Hydra

有一天，Petya 收到了妈妈送的生日礼物：一本名为《图论的传奇与神话》的书。从这本书里，Petya 了解到了一种叫做 hydra 的图结构。 如果一个无向图有如下结构，则它被称为 hydra：如图所示，有两个点 $u$ 和 $v$ 被一条边连接，分别被称作 hydra 的“胸部”和“胃部”。胸部与 $h$ 个点相连，这些点是 hydra 的“头”，胃部与 $t$ 个点相连，这些点是 hydra 的“尾”。注意，hydra 是一个包含 $h + t + 2$ 个点的树。  此外，Petya 还得到了一个无向图 $G$，包含 $n$ 个点和 $m$ 条边，这是去年妈妈送他的生日礼物。图 $G$ 没有自环和重边。 现在，Petya 想要找出图 $G$ 中是否存在 hydra。如果存在，输出 hydra 的结构；如果不存在，请说明该图不包含 hydra。

第一行包含四个整数 $n$、$m$、$h$、$t$（$1 \leq n, m \leq 10^{5}$，$1 \leq h, t \leq 100$）——分别表示图 $G$ 的点数、边数，以及 hydra 的头数和尾数。 接下来的 $m$ 行每行包含两个整数 $a_i$ 和 $b_i$（$1 \leq a_i, b_i \leq n$，$a_i \neq b_i$），表示连接的两个点。 保证图中不存在自环和重边。图中所有点编号为 $1$ 到 $n$。

如果图 $G$ 中不存在 hydra，输出一行 “NO”。 否则，第一行输出 “YES”。第二行输出两个整数 $u$ 和 $v$，表示胸部和胃部的编号。第三行输出 $h$ 个整数——作为头的点编号。第四行输出 $t$ 个整数——作为尾的点编号。以上所有编号须两两不同。 如果有多种可能的解，你可以输出任意一种。

第一个样例可见下方图片：  由 ChatGPT 5 翻译