English · Original
Chinese · Translation
Formal · Original
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.
## Input
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).
## Output
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.
[samples]
给定一个包含 #cf_span[n] 个顶点和 #cf_span[m] 条边的无向连通图。图中无自环和重边。
你还被给定两个不同的顶点 #cf_span[s] 和 #cf_span[t]，以及两个值 #cf_span[ds] 和 #cf_span[dt]。你的任务是构建该图的任意一棵生成树（注意图是无权的），使得顶点 #cf_span[s] 的度数不超过 #cf_span[ds]，且顶点 #cf_span[t] 的度数不超过 #cf_span[dt]；或者确定这样的生成树不存在。
图 #cf_span[G] 的 _生成树_ 是一个子图，它是一棵树且包含图 #cf_span[G] 的所有顶点。换句话说，它是一个包含 #cf_span[n - 1] 条边的连通图，可以通过从 #cf_span[G] 中删除一些边得到。
一个顶点的度数是指与该顶点相关联的边的数量。
输入的第一行包含两个整数 #cf_span[n] 和 #cf_span[m] (#cf_span[2 ≤ n ≤ 200 000], #cf_span[1 ≤ m ≤ min(400 000, n·(n - 1) / 2)]) —— 图的顶点数和边数。
接下来的 #cf_span[m] 行描述了图的边。每行包含两个整数 #cf_span[u] 和 #cf_span[v] (#cf_span[1 ≤ u, v ≤ n], #cf_span[u ≠ v]) —— 对应边的两个端点。保证图中无自环、无重边，且连通。
最后一行包含四个整数 #cf_span[s], #cf_span[t], #cf_span[ds], #cf_span[dt] (#cf_span[1 ≤ s, t ≤ n], #cf_span[s ≠ t], #cf_span[1 ≤ ds, dt ≤ n - 1])。
如果无解，请在输出的唯一一行中打印 "_No_"（不含引号）。
否则，在第一行打印 "_Yes_"（不含引号）。接下来的 #cf_span[(n - 1)] 行每行打印两个整数，表示生成树的边。生成树的每条边必须恰好输出一次。
你可以按任意顺序输出边，每条边的两个端点也可以按任意顺序输出。
如果有多个解，输出任意一个即可。
## Input
输入的第一行包含两个整数 #cf_span[n] 和 #cf_span[m] (#cf_span[2 ≤ n ≤ 200 000], #cf_span[1 ≤ m ≤ min(400 000, n·(n - 1) / 2)]) —— 图的顶点数和边数。接下来的 #cf_span[m] 行描述了图的边。每行包含两个整数 #cf_span[u] 和 #cf_span[v] (#cf_span[1 ≤ u, v ≤ n], #cf_span[u ≠ v]) —— 对应边的两个端点。保证图中无自环、无重边，且连通。最后一行包含四个整数 #cf_span[s], #cf_span[t], #cf_span[ds], #cf_span[dt] (#cf_span[1 ≤ s, t ≤ n], #cf_span[s ≠ t], #cf_span[1 ≤ ds, dt ≤ n - 1])。
## Output
如果无解，请在输出的唯一一行中打印 "_No_"（不含引号）。否则，在第一行打印 "_Yes_"（不含引号）。接下来的 #cf_span[(n - 1)] 行每行打印两个整数，表示生成树的边。生成树的每条边必须恰好输出一次。你可以按任意顺序输出边，每条边的两个端点也可以按任意顺序输出。如果有多个解，输出任意一个即可。
[samples]
**Definitions**
Let $ G = (V, E) $ be an undirected connected graph with $ |V| = n $, $ |E| = m $, no loops, and no multiple edges.
Let $ s, t \in V $, $ s \ne t $, and $ d_s, d_t \in \mathbb{Z}^+ $ with $ 1 \le d_s, d_t \le n-1 $.
**Constraints**
1. $ 2 \le n \le 200{,}000 $
2. $ 1 \le m \le \min(400{,}000, \frac{n(n-1)}{2}) $
3. $ 1 \le s, t \le n $, $ s \ne t $
4. $ 1 \le d_s, d_t \le n-1 $
**Objective**
Find a spanning tree $ T = (V, E_T) $ of $ G $, where $ |E_T| = n-1 $, such that:
$$
\deg_T(s) \le d_s \quad \text{and} \quad \deg_T(t) \le d_t
$$
If no such spanning tree exists, output "No". Otherwise, output "Yes" and the $ n-1 $ edges of $ T $.
API Response (JSON)
{
"problem": {
"name": "F. st-Spanning Tree",
"description": {
"content": "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 ",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 4000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF723F"
},
"statements": [
{
"statement_type": "Markdown",
"content": "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.\n\nYou are also given two distinct vertices _s_ and _t_, and ...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "给定一个包含 #cf_span[n] 个顶点和 #cf_span[m] 条边的无向连通图。图中无自环和重边。\n\n你还被给定两个不同的顶点 #cf_span[s] 和 #cf_span[t]，以及两个值 #cf_span[ds] 和 #cf_span[dt]。你的任务是构建该图的任意一棵生成树（注意图是无权的），使得顶点 #cf_span[s] 的度数不超过 #cf_span[ds]，且顶点 #cf...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ G = (V, E) $ be an undirected connected graph with $ |V| = n $, $ |E| = m $, no loops, and no multiple edges. \nLet $ s, t \\in V $, $ s \\ne t $, and $ d_s, d_t \\in \\mathbb{Z}^+...",
"is_translate": false,
"language": "Formal"
}
]
}