← 返回题目列表

Codeforces · 243/B

B. 九头蛇

中文机器翻译题面 查看原题

有一天,Petya 从他妈妈那里得到了一份生日礼物:一本叫做《图论的传奇与神话》的书。 Petya 从这本书中了解了九头蛇图。

无向图是一个九头蛇,如果它有一个结构,如下图所示。即有两个节点u和v通过边相连,它们分别是水螅的胸部和胃部。胸部与 h 节点相连,即九头蛇的头部。胃与t结相连,t结是水螅的尾巴。请注意,Hydra 是一棵树,由 h + t + 2 个节点组成。

另外,Petya 有一个无向图 G,由 n 个节点和 m 个边组成。佩蒂亚从他妈妈那里得到了这张图表作为去年的生日礼物。图 G 不包含自环或重边。

现在 Petya 想要在图 G 中找到九头蛇。或者,确保该图没有九头蛇。

输入

第一行包含四个整数 n, m, h, t (1 ≤ n, m ≤ 105, 1 ≤ h, t ≤ 100) — 图 G 中节点和边的数量,以及九头蛇头和尾的数量。

接下来的 m 行包含图 G 的边的描述。这些行中的第 i 行包含两个整数 ai 和 bi (1 ≤ ai, bi ≤ n, a ≠ b) — 由第 i 条边连接的节点数。

保证图G不包含自环和重边。考虑用 1 到 n 的整数编号的图 G 的节点。

输出

如果图 G 没有九头蛇,则打印“NO”(不带引号)。

否则,在第一行打印“YES”(不带引号)。在第二行中打印两个整数——节点 u 和 v 的数量。在第三行中打印 h 数字——作为头的节点的数量。在第四行中打印 t 个数字 — 尾部节点的编号。所有打印的数字应该是不同的。

如果有多个可能的答案,您可以打印其中任何一个。

示例

输入 #1

9 12 2 3
1 2
2 3
1 3
1 4
2 5
4 5
4 6
6 5
6 7
7 5
8 7
9 1

输出 #1

YES
4 1
5 6
9 3 2

输入 #2

7 10 3 3
1 2
2 3
1 3
1 4
2 5
4 5
4 6
6 5
6 7
7 5

输出 #2

NO

注意

第一个示例如下图所示: