U517657 「Cfz Round 5」Mata rainen (English)

[Chinese Statement](https://www.luogu.com.cn/problem/P11486). **You must submit your code at the Chinese version of the statement.** --- The title means: See you next year. Rose is a girl in her third year of senior high school. During the summer vacation before entering her third year, she reviewed *The Story of Guo Tuotuo Who Plants Trees* (an ancient Chinese article) and then created this tree-related problem. After submitting this problem to the problem-setting team, she decided to devote all her time and energy to preparing for the college entrance examination, looking forward to meeting everyone again in algorithm competitions during the summer vacation of 2025.

Please determine whether there exists a tree that satisfies the following conditions. If so, please try to construct it. The tree contains $n$ vertices numbered from $1$ to $n$. Additionally, $m$ pairs of vertices $(s_i, t_i)$ are given, and it is required that these $m$ paths from vertex $s_i$ to vertex $t_i$ cover each edge **exactly** once $^\dagger$. **If you correctly determine whether there is a solution but cannot construct the tree, you can still obtain some points. See *Scoring Method* part for details.** $\dagger$ A path from vertex $s$ to vertex $t$ covers an edge $(u, v)$ if and only if edge $(u, v)$ is on the shortest path from vertex $s$ to vertex $t$.

无

无

#### Sample Explanation #1  The top left diagram shows the tree given in the sample output. Edges $(1,5)$ and $(5,2)$ are covered by path $(1,2)$, and edges $(3,5)$, $(5,6)$, and $(6,4)$ are covered by path $(3,4)$, which meets the problem requirements. In the top right diagram, edge $(5,6)$ is covered by both paths $(1,2)$ and $(3,4)$, which does not meet the problem requirements. In the bottom left diagram, edge $(5,6)$ is not covered by any path, which does not meet the problem requirements. The bottom right diagram is not a tree, which does not meet the problem requirements. #### Sample Explanation #2 It can be proven that there is no tree that meets the requirements. #### Scoring Method This problem uses special judge for evaluation. For each test case: - If the first line has the wrong format or does not match the answer (case-insensitive), you will receive $0\%$ of the points. - If the first line is correct and says "No", you will receive $100\%$ of the points. - If the first line is correct and says "Yes", **but the format of the following $n-1$ lines is incorrect**, you will receive $0\%$ of the points. Therefore, **please ensure that the output forms a tree**. - If the first line is correct and says "Yes", the format of the following $n-1$ lines is correct, but the tree does not meet the requirements, you will receive $20\%$ of the points. - If the first line is correct and says "Yes", the format of the following $n-1$ lines is correct, and the tree meets the requirements, you will receive $100\%$ of the points. That is, for the first sample, on the basis of correctly outputting "Yes", outputting the top left diagram will give full points, outputting the top right and bottom left diagrams will give $20\%$ of the points, and outputting the bottom right diagram will not give any points; for the second sample, correctly outputting "No" will give full points. #### Constraints For all test data, it is guaranteed that: - $2 \leq n \leq 3 \times 10^5$; - $1 \leq m \leq 3 \times 10^5$; - $1 \leq s_i, t_i \leq n$ and $s_i \neq t_i$. **Subtasks are used in this task.** - Subtask 0 (10 points): $n \leq 3$, $m \leq 3$. - Subtask 1 (10 points): $n \leq 10$, $m \leq 10$. - Subtask 2 (20 points): $m = 1$. - Subtask 3 (10 points): $n \leq 300$, $m \leq 300$. - Subtask 4 (10 points): $n \leq 2 \times 10^3$, $m \leq 2 \times 10^3$. - Subtask 5 (20 points): $m \leq 2 \times 10^3$. - Subtask 6 (20 points): No further restrictions.