370. Is This Graph a Tree

Core1000 ms256 MBSolved by 0%

Print Yes if the graph is a tree and No otherwise.

A tree is a graph that is connected and has no cycle. That is two conditions, and the entire difficulty of this problem is that students check one and stop.

There is a shortcut worth knowing, and it is exact: a graph on n vertices is a tree exactly when it is connected AND has exactly n - 1 edges. Either condition alone is not enough. Look at the second sample: three vertices in a triangle plus one lone vertex is 3 edges on 4 vertices, so the edge count is right and the graph is still not a tree.

So count components, using the traversal from problem 363, and compare m against n - 1. Both must hold.

Constraints - `1 ≤ n ≤ 100000` - `0 ≤ m ≤ 200000` - There are no self-loops and no repeated edges.

Input

The first line contains two integers n and m, the number of vertices and edges. Each of the next m lines contains two integers u and v, an undirected edge between those vertices. Vertices are numbered 1 to n.

Output

Print Yes or No on one line.

Input4 3 1 2 2 3 3 4

OutputYes

Noteis a path, which is a tree

Input4 3 1 2 2 3 1 3

OutputNo

Notehas exactly n minus 1 edges but is a triangle plus a lone vertex, so the edge count alone is not enough

Input3 3 1 2 2 3 3 1

OutputNo

Noteis connected but has a cycle, so connectedness alone is not enough either

Hint 1Approach

Hint 2Approach

Hint 3Pseudocode

Hint 4Full solution