Mirror-Symmetric Tree Graph

Time limit1sMemory limit128 MB

Summary
Decide whether a given connected graph can be formed by gluing a rooted tree to its mirrored copy at every non-root leaf.
Level

Medium6 of 10

Topics
Graph, Tree, DFS
Solved
No attempts yet

Problem

Let T be a rooted tree, and let S be an exact copy of T. For every leaf of T except the root, identify that leaf with the corresponding leaf of S. The graph obtained this way is called a mirror-symmetric tree graph.

Given an undirected connected graph, determine whether it is a mirror-symmetric tree graph.

Input

The first line contains two integers N and M, the number of vertices and the number of edges. The vertices are numbered from 1 to N.

Each of the next M lines contains two integers x and y, describing one edge. The vertices x and y are distinct, and there is at most one edge between any pair of vertices.

Output

Print YES if the given graph is a mirror-symmetric tree graph. Otherwise, print NO.

Constraints

  • 3 ≤ N, M ≤ 100,000
  • 1 ≤ x, y ≤ N
  • x ≠ y

Examples3

  1. Example 1

    Input
    7 7
1 2
2 3
3 4
4 5
5 6
6 7
7 1
    Expected output
    NO

  2. Example 2

    Input
    6 6
1 2
2 3
2 4
3 5
4 5
5 6
    Expected output
    YES

  3. Example 3

    Input
    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
    Expected output
    YES