Cây khung st

Cho một đồ thị vô hướng liên thông gồm $n$ đỉnh và $m$ cạnh, không có khuyên và không có cạnh lặp. Cho thêm hai đỉnh phân biệt $s$, $t$ và hai số $d_s$, $d_t$.

Hãy chọn ra một cây khung của đồ thị (gồm đúng $n-1$ cạnh của đồ thị, nối tất cả các đỉnh và không có chu trình) sao cho bậc của đỉnh $s$ trong cây không vượt quá $d_s$ và bậc của đỉnh $t$ trong cây không vượt quá $d_t$, hoặc cho biết không tồn tại cây khung như vậy.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên $n$ và $m$.
• $m$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u$, $v$ mô tả một cạnh nối hai đỉnh $u$ và $v$.
• Dòng cuối cùng chứa bốn số nguyên $s$, $t$, $d_s$, $d_t$.

Dữ liệu ra

Nếu không tồn tại cây khung thỏa mãn, in ra No.

Ngược lại, dòng đầu tiên in ra Yes, sau đó in $n-1$ dòng, mỗi dòng gồm hai số nguyên là hai đầu mút của một cạnh trong cây khung. Mỗi cạnh của cây được in đúng một lần, các cạnh có thể in theo thứ tự bất kỳ và hai đầu mút của mỗi cạnh cũng có thể in theo thứ tự bất kỳ.

Nếu có nhiều đáp án, in ra đáp án bất kỳ.

Ràng buộc

• $2\le n\le 2·{10}^5$
• $1\le m\le min(4·{10}^5,\frac{n(n-1)}{2})$
• $1\le u,v\le n$, $u\ne v$; đồ thị liên thông, không có cạnh lặp
• $1\le s,t\le n$, $s\ne t$
• $1\le d_s,d_t\le n-1$

Ví dụ