「Cfz Round 5」Mata rainen

[English statement](https://www.luogu.com.cn/problem/U517657). **You must submit your code at the Chinese version of the statement.** --- **如您希望对本题难度评分、数据强度等事项提出宝贵意见，请移步 [关于本题难度评分、数据强度等事项的说明](https://www.luogu.com.cn/discuss/1030705)，而不要新开帖子！**（2024.12.30 rui_er 添加，本条保留至 2025.1.31） --- 题目名称意为：明年见。 小 R 是一个正在上高三的女孩子。她在升入高三的暑假复习了[《种树郭橐（tuó）驼传》](https://baike.baidu.com/item/%E7%A7%8D%E6%A0%91%E9%83%AD%E6%A9%90%E9%A9%BC%E4%BC%A0)，便编出了这道与树有关的题。 在把这道题目丢给出题组后，她决定把全部时间和精力投入到高考的旅程中，期待在 2025 年的暑假在算法竞赛中与大家再会。

请判断是否存在一棵树满足如下条件。若存在，请尝试给出构造。 树中包含 $n$ 个结点，编号为 $1\sim n$。另外，给定 $m$ 个点对 $(s_i,t_i)$，要求树上这 $m$ 条从点 $s_i$ 到点 $t_i$ 的路径覆盖每条边**恰好**一次 $^\dagger$。 **若你正确判断了是否有解，但不会构造出这棵树，也可以获得一定的分数，详见【评分方式】。** $\dagger$ 称从点 $s$ 到点 $t$ 的路径覆盖一条边 $(u,v)$，当且仅当边 $(u,v)$ 在点 $s$ 到点 $t$ 的最短路径上。

第一行包含两个整数 $n,m$，表示这棵树的点数和给出的点对数。 接下来 $m$ 行，每行两个整数 $s_i,t_i$，表示一个点对。

第一行输出一个字符串 `Yes` 或 `No`（大小写不敏感），表示是否有解。 若有解，继续输出 $n-1$ 行，每行包含两个整数 $u_i,v_i$，描述一条边。**你需要保证 $\bm{1\le u_i,v_i\le n}$ 且所有边构成一棵树。**

6 2
1 2
3 4

Yes
1 5
2 5
3 5
4 6
5 6

3 3
1 2
2 3
1 3

No

#### 「样例解释 #1」  左上图为样例输出中给出的树。边 $(1,5),(5,2)$ 被路径 $(1,2)$ 覆盖，边 $(3,5),(5,6),(6,4)$ 被路径 $(3,4)$ 覆盖，符合题目要求。 右上图中边 $(5,6)$ 被路径 $(1,2)$ 和 $(3,4)$ 覆盖，不符合题目要求。 左下图中边 $(5,6)$ 未被任何路径覆盖，不符合题目要求。 右下图不是一棵树，不符合题目要求。 #### 「样例解释 #2」 可以证明不存在符合要求的树。 #### 「评分方式」 本题采用自定义校验器（Special Judge）进行评测。 对于每个测试点： - 若第一行格式错误或与答案不匹配（大小写不敏感），得 $0\%$ 的分数。 - 若第一行答案正确且为 `No`，得 $100\%$ 的分数。 - 若第一行答案正确且为 `Yes`，**但后 $n-1$ 行格式错误**，得 $0\%$ 的分数。 因此，**请务必保证输出为一棵树**。 - 若第一行答案正确且为 `Yes`，后 $n-1$ 行格式正确但树不符合要求，得 $20\%$ 的分数。 - 若第一行答案正确且为 `Yes`，后 $n-1$ 行格式正确且树符合要求，得 $100\%$ 的分数。 也就是说，对于第一个样例，在正确输出 `Yes` 的基础上，输出左上图可以得到满分，输出右上图、左下图可以得到 $20\%$ 的分数，输出右下图不能得到任何分数；对于第二个样例，正确输出 `No` 即可得到满分。 #### 「数据范围」 对于所有测试数据，保证： - $2\le n\le 3\times 10^5$； - $1\le m\le 3\times 10^5$； - $1\le s_i,t_i\le n$ 且 $s_i\ne t_i$。 **本题采用捆绑测试。** - Subtask 0（10 points）：$n\le 3$，$m\le 3$。 - Subtask 1（10 points）：$n\le 10$，$m\le 10$。 - Subtask 2（20 points）：$m=1$。 - Subtask 3（10 points）：$n\le 300$，$m\le 300$。 - Subtask 4（10 points）：$n\le 2\times 10^3$，$m\le 2\times 10^3$。 - Subtask 5（20 points）：$m\le 2\times 10^3$。 - Subtask 6（20 points）：无特殊限制。 #### 「Hack 数据」 本题于赛后添加了部分 Hack 数据。这些数据均满足 Subtask 6 对数据规模的限制，他们被添加到 Subtask 7 中。这些数据不计分，但只有通过所有数据，才算做 AC 本题。 - Subtask 7（0 points）：赛后添加的 Hack 数据。