← 返回题目列表

Codeforces · 723/F

F. st 生成树

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

给定一个由 n 个顶点和 m 个边组成的无向连通图。图中没有循环,也没有多重边。

您还将获得两个不同的顶点 s 和 t,以及两个值 ds 和 dt。你的任务是构建给定图的任意生成树(注意图没有加权),使得顶点 s 的度数不超过 ds,顶点 t 的度数不超过 dt,或者确定不存在这样的生成树。

图G的生成树是一个子图,它是一棵树,包含图G的所有顶点。换句话说,它是一个包含n-1条边的连通图,可以通过从G中删除一些边来获得。

顶点的度数是入射到该顶点的边的数量。

输入

输入的第一行包含两个整数 n 和 m (2 ≤ n ≤ 200 000, 1 ≤ m ≤ min(400 000, n·(n - 1) / 2)) — 图中的顶点数和边数。

接下来的 m 行包含图的边的描述。每条线包含两个整数 u 和 v (1 ≤ u, v ≤ n, u ≠ v) - 相应边的末端。保证图不包含环、不存在重边并且是连通的。

最后一行包含四个整数 s, t, ds, dt (1 ≤ s, t ≤ n, s ≠ t, 1 ≤ ds, dt ≤ n - 1)。

输出

如果答案不存在,则在输出的唯一行中打印“No”(不带引号)。

否则,在第一行打印“Yes”(不带引号)。在接下来的 (n - 1) 行中,每一行打印两个整数 - 生成树边缘的描述。生成树的每个边必须恰好打印一次。

您可以按任意顺序输出边。您可以按任意顺序输出每条边的末端。

如果有多个解决方案,请打印其中任何一个。

示例

输入 #1

3 3
1 2
2 3
3 1
1 2 1 1

输出 #1

Yes
3 2
1 3

输入 #2

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

输出 #2

Yes
1 3
5 7
3 2
7 4
2 4
6 1