[BalticOI 2011 Day2] Tree Mirroring
题意翻译
题目描述
T是一棵树(一个连通的无向图),并且S是一个完美的复制品(与T完全相同)。构造一个新的图T和S,并合并相应的叶节点(但绝不合并根)。我们称这样的图为树之镜像图.
输入输出格式
输入格式:
输入的第一行包含两个整数。N和M,表示图G的顶点和边数。
接下来有M行,每一行包含两个正整数:x和y (x≠y且 1≤x,y≤N)表示顶点X和Y之间有一条边。且在任意一对顶点之间最多有一条边。
输出格式:
输出只有一行,判断图G是否是一个树之镜像图,是输出yes,否则输出no。
Translated by @找寻
题目描述
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.
输入输出样例
输入样例 #1
7 7
1 2
2 3
3 4
4 5
5 6
6 7
7 1
输出样例 #1
NO
输入样例 #2
6 6
1 2
2 3
2 4
3 5
4 5
5 6
输出样例 #2
YES
输入样例 #3
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
输出样例 #3
YES
说明
对于 $30\%$ 的数据,$3 \le N,M \le 300$。
对于 $60\%$ 的数据,$3 \le N,M \le 3500$。
对于所有数据,$3 \le N,M \le 10^5$。