st-Spanning Tree
题号:NC245488
时间限制:C/C++/Rust/Pascal 4秒,其他语言8秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
Special Judge, 64bit IO Format: %lld

题目描述

给定一个n个点m条边的无向联通图,没有重边和自环。给定s和t,求一棵生成树,使得s,t的度数不超过ds,dt。
若有解,输出“Yes”和方案,若无解,输出“No”。

输入描述:

第一行两个整数
接下来m行每行两个整数表示一条边。
最后一行四个整数s , t , , ( , , ).

输出描述:

如果有解,请在第一行输出Yes,之后输出n-1行,每行两个数字代表生成树中的一条边。
如果无解,请输出No。
示例1

输入

复制
3 3
1 2
2 3
3 1
1 2 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

输出

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