{"problem":{"name":"水影若深蓝","description":{"content":"在梦里，在朦胧的水影中，帆帆看见了这棵只属于他的深蓝之树。 当一切梦沉寂，他却遗忘了所有，只记得树上有 $n$ 个结点。 真的吗？似乎并没有，有 $m$ 件事情他一直牢记着，第 $i$ 件事情是：节点 $u_i$ 和 $v_i$ 在这棵深蓝之树上唯一的不重复经过某个点的路径恰好有两条边。 那么，你能否帮助帆帆想起来这棵深蓝之树的样子呢，如果有多个可能的，你只需要输出任意一种。 当然，帆帆也","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P4"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10179"},"statements":[{"statement_type":"Markdown","content":"在梦里，在朦胧的水影中，帆帆看见了这棵只属于他的深蓝之树。\n\n当一切梦沉寂，他却遗忘了所有，只记得树上有 $n$ 个结点。\n\n真的吗？似乎并没有，有 $m$ 件事情他一直牢记着，第 $i$ 件事情是：节点 $u_i$ 和 $v_i$ 在这棵深蓝之树上唯一的不重复经过某个点的路径恰好有两条边。\n\n那么，你能否帮助帆帆想起来这棵深蓝之树的样子呢，如果有多个可能的，你只需要输出任意一种。\n\n当然，帆帆也是会磨损的，因此当你发现无论如何都找不到满足帆帆这 $m$ 件事情的深蓝之树时，你需要报告无解。\n\n## Input\n\n**本题有多组数据**。\n\n第一行一个正整数 $T$ 表示数据组数。\n\n对于每组数据：\n\n第一行两个非负整数 $n,m$ 表示树上的点数和帆帆记忆中事件个数。\n\n接下来 $m$ 行，每行两个正整数 $u_i,v_i$ 表示一个事件。\n\n## Output\n\n对于每组数据：\n\n- 若不存在符合条件的树，输出 `No`。\n- 否则，第一行输出 `Yes`，接下来 $n-1$ 行输出 $n-1$ 对正整数 $(u,v)$，表示你给出的树上的 $n-1$ 条边。\n\n本题采用 `special judge` 评测，也就是说，如果有多种可能的答案，你可以输出任意一种。\n\n[samples]\n\n## Background\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/e2h3lfb4.png)\n\n帆帆爱明日方舟，更爱水月和深蓝之树。但在龙年，他想构建一棵独属于他的深蓝之树。\n\n## Note\n\n### 样例 $1$ 解释\n\n对于第一组数据，不难验证给出的树符合条件。\n\n对于第二组数据，可以证明不存在符合条件的树。\n\n### 测试点约束\n\n对于 $100\\%$ 的数据，$1\\le T\\le 10^5$，$n\\ge 2$，$m\\ge 0$，$1\\le \\sum n\\le 3\\times 10^5$，$0\\le \\sum m\\le 3\\times 10^5$，$1\\le u_i,v_i\\le n$，$u_i\\neq v_i$。\n\n本题采用捆绑测试。\n\n| 子任务编号 | 特殊限制 | 分值 |\n| :--------: | :-------------: | :--: |\n| Subtask #1 |     $\\sum n,\\sum m\\le 9$     | $10$ |\n| Subtask #2 |    $\\sum n,\\sum m\\le 50$     | $10$ |\n| Subtask #3 |    $\\sum n,\\sum m\\le 5000$    | $10$ |\n| Subtask #4 |   $v_i=u_i+1$    | $10$ |\n| Subtask #5 |   $u_i=1$    | $10$ |\n| Subtask #6 |   $u_i\\neq 1,v_i\\neq 1$    | $10$ |\n| Subtask #7 |   $T=1$    | $10$ |\n| Subtask #8 |   无    | $30$ |","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10179","tags":["洛谷原创","Special Judge","O2优化","洛谷月赛"],"sample_group":[["2\n4 2\n1 2\n3 4\n3 3\n1 2\n2 3\n3 1","Yes\n1 3\n2 4\n2 3\nNo"]],"created_at":"2026-03-03 11:09:25"}}