CF723F.st-Spanning Tree

You are given an undirected connected graph consisting of n vertices and m edges. There are no loops and no multiple edges in the graph.

You are also given two distinct vertices s and t, and two values d__s and d__t. Your task is to build any spanning tree of the given graph (note that the graph is not weighted), such that the degree of the vertex s doesn't exceed d__s, and the degree of the vertex t doesn't exceed d__t, or determine, that there is no such spanning tree.

The spanning tree of the graph G is a subgraph which is a tree and contains all vertices of the graph G. In other words, it is a connected graph which contains n - 1 edges and can be obtained by removing some of the edges from G.

The degree of a vertex is the number of edges incident to this vertex.

给你一个包含 $n$ 个顶点和 $m$ 条边的无向连通图。图中不含自环，也不含重边。

你还给定了两个不同的顶点 $s$ 和 $t$，以及两个数值 $d_s$ 和 $d_t$。你的任务是：构造该图的任意一棵生成树（注意：该图无边权），使得顶点 $s$ 的度数不超过 $d_s$，且顶点 $t$ 的度数不超过 $d_t$；若不存在满足条件的生成树，则判定其不存在。

图 $G$ 的生成树是指 $G$ 的一个子图，该子图本身是一棵树，且包含 $G$ 的所有顶点。换言之，它是一个连通图，恰好包含 $n-1$ 条边，且可通过从 $G$ 中删去若干条边得到。

一个顶点的度数是指与该顶点关联的边的数量。

The first line of the input contains two integers n and m (2 ≤ n ≤ 200 000, 1 ≤ m ≤ min(400 000, n·(n - 1) / 2)) — the number of vertices and the number of edges in the graph.

The next m lines contain the descriptions of the graph's edges. Each of the lines contains two integers u and v (1 ≤ u, v ≤ n, u ≠ v) — the ends of the corresponding edge. It is guaranteed that the graph contains no loops and no multiple edges and that it is connected.

The last line contains four integers s, t, d__s, d__t (1 ≤ s, t ≤ n, s ≠ t, 1 ≤ d__s, d__t ≤ n - 1).

输入的第一行包含两个整数 $n$ 和 $m$（$2 \leq n \leq 200\,000$，$1 \leq m \leq \min(400\,000,\, n\cdot(n - 1)/2)$）—— 分别表示图中顶点的数量和边的数量。

接下来的 $m$ 行描述图中的各条边。每行包含两个整数 $u$ 和 $v$（$1 \leq u,\,v \leq n$，$u \neq v$）—— 表示对应边的两个端点。保证图中不含自环和重边，且图是连通的。

最后一行包含四个整数 $s$、$t$、$d_s$、$d_t$（$1 \leq s,\,t \leq n$，$s \neq t$，$1 \leq d_s,\,d_t \leq n - 1$）。

If the answer doesn't exist print "No" (without quotes) in the only line of the output.

Otherwise, in the first line print "Yes" (without quotes). In the each of the next (n - 1) lines print two integers — the description of the edges of the spanning tree. Each of the edges of the spanning tree must be printed exactly once.

You can output edges in any order. You can output the ends of each edge in any order.

If there are several solutions, print any of them.

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

否则，在第一行打印“Yes”（不带引号）；接下来的 $n-1$ 行中，每行打印两个整数——表示生成树的一条边。生成树的每条边必须恰好输出一次。

边的输出顺序任意；每条边的两个端点的输出顺序也任意。

若存在多个解，输出任意一个即可。