题目描述

Let $T$ be a rooted tree (a connected undirected acylic graph), and let $S$ be a perfect copy of $T$. Construct a new graph by taking the union of $T$ and $S$, and merging the corresponding leaf nodes (but never the root). We call such a graph a tree-mirrored graph.

输入格式

The first line of input contains two integers $N$ and $M$, the number of vertices and edges of a graph $G$. The vertices in $G$ are labeled from $1$ to $N$. The following $M$ lines describe the edges. Each such line contains two integers $x$ and $y(x≠y;1 \le x,y \le N)$, describing one edge. There will be at most one edge between any pair of vertices.

输出格式

The first and only line of output should contain the string YES if the graph $G$ is a tree-mirrored graph, and NO otherwise.

题目大意

题目描述

T是一棵树(一个连通的无向图)，并且S是一个完美的复制品(与T完全相同)。构造一个新的图T和S，并合并相应的叶节点(但绝不合并根)。我们称这样的图为树之镜像图.

输入输出格式

输入格式：

输入的第一行包含两个整数。N和M，表示图G的顶点和边数。

接下来有M行，每一行包含两个正整数：x和y (x≠y且 1≤x,y≤N)表示顶点X和Y之间有一条边。且在任意一对顶点之间最多有一条边。

输出格式：

输出只有一行，判断图G是否是一个树之镜像图，是输出yes，否则输出no。

Translated by @找寻

7 7
1 2
2 3
3 4
4 5
5 6
6 7
7 1

NO

6 6
1 2
2 3
2 4
3 5
4 5
5 6

YES

22 28
13 8
8 1
1 22
1 12
1 14
13 18
13 4
4 20
20 7
13 15
15 3
15 9
9 16
9 19
22 5
12 5
14 5
5 11
11 6
18 6
7 10
10 17
17 6
3 21
21 6
16 2
19 2
2 21

YES

提示

对于 $30\%$ 的数据，$3 \le N,M \le 300$。

对于 $60\%$ 的数据，$3 \le N,M \le 3500$。

对于所有数据，$3 \le N,M \le 10^5$。