给定一个由 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