Вам задан связный неориентированный граф, состоящий из n вершин и m рёбер. Каждое ребро соединяет две различные вершины, любую пару вершин соединяет не более одного ребра.
Также вам даны две различные вершины s и t, а также две величины ds и dt. Перед вами стоит задача построить любой остов заданного графа (обратите внимание, что граф невзвешенный), у которого степень вершины s не превышает ds, а степень вершины t не превышает dt, либо сообщить, что это невозможно.
Остов (покрывающее дерево) графа G — такой его подграф, который является деревом и содержит все вершины графа G. Иными словами, это связный граф, содержащий n - 1 ребро и полученный из заданного графа G удалением некоторых рёбер.
Степенью вершины называется число инцидентных этой вершине рёбер.
Выходные данные
Если ответа не существует, выведите в первую строку «No» (без кавычек).
В противном случае в первую строку выведите «Yes» (без кавычек). В следующей (n - 1)-й строке выведите по два целых числа — описание рёбер остова. Каждое из рёбер остова должно быть выведено ровно один раз.
Выводить ребра можно в любом порядке. Концы ребер также можно выводить в любом порядке.
Если решений несколько, выведите любое из них.
Примеры
| № | Входные данные | Выходные данные |
|
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
|