Baltic Olympiad in Informatics: 2011 Day 2, Problem 4

Let $T$ be a rooted tree (a connected undirected acyclic 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.

Write a program that determines if an arbitrary undirected connected graph is a tree-mirrored graph.

Constraints

$3\le N,M\le {10}^5$

Subtask 1 [30%]

$3\le N,M\le 300$

Subtask 2 [30%]

$3\le N,M\le 3500$

Subtask 3 [40%]

No additional constraints.

Input Specification

The first line of input contains two space-separated 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 space-separated integers $x$ and $y$ $(x\ne y;1\le x,y\le N)$, describing one bidirectional edge. There will be at most one edge between any pair of vertices.

Output Specification

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

Sample Input 1

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

Sample Output 1

NO

Sample Input 2

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

Sample Output 2

YES

Sample Input 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

Sample Output 3

YES

Explanation for Sample 3

The last example input corresponds to the graph in Figure 1.