Ainz is a master player of the DMMORPG Yggdrasil. Currently, he is preparing to class up!
The classes in Yggdrasil form a forest: that is, there exists at most 1 path between each pair of nodes. However, Ainz finds that someone has used a world item to add some number of extra edges!
Ainz can use the skill «Wish Upon a Star» to remove at most a single edge. He then asks you: is it possible to restore the graph to a forest?
Subtask 1 [20%]
~1 \leq N, M \leq 5\,000~
Subtask 2 [80%]
~1 \leq N, M \leq 200\,000~
The first line of input will contain two space separated integers, ~N~ and ~M~, respectively.
The next ~M~ lines will each contain two space separated integers, ~a_i~ and ~b_i~, indicating there exists a bidirectional edge from ~a_i~ to ~b_i~.
YES if the graph can be restored to a forest by removing at most one edge, and
Sample Input 1
5 4 1 2 1 3 4 5 2 3
Sample Output 1
Explanation for Sample Output 1
Removing the edge ~2\to 3~ makes the graph a forest.
Sample Input 2
4 2 1 2 3 4
Sample Output 2
Explanation for Sample Output 2
The graph is already a forest.