Chef Land

All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
You are given an undirected unweighted graph consisting of N nodes and M edges. A pair of nodes u, v is called good if and only if you can go from node u to v and then return back from v to u without using any edge more than once.
Can you add at most one edge to the graph to make all the pairs of nodes good? Note that the added edge can be between two vertices which are already connected by some edges. However you are not allowed to add self loops.
Input
First line of the input contains two space separated integers  N (number of nodes) and M (number of edges).
Each of the next M lines contains two space separated integers x and y, denoting that there is an edge between node x and y.
Output
Output "YES" (without quotes) if it possible to make all pairs of node good by adding at most one edge. Output "NO" (without quotes) otherwise.
Constraints
 1 ≤ N ≤ 10^{5}
 0 ≤ M ≤ 2 * 10^{5}
 1 ≤ x, y ≤ N
 It is guaranteed that the graph is connected.
 The given graph may contain multiedges. It doesn't contain any self loops.
Example
Input: 4 4 3 2 3 1 2 1 1 4 Output: YES
Explanation
We can connect nodes 3 and 4 via an edge. After that all the pair of vertices will be good.
Author:  kingofnumbers 
Tester:  mgch 
Editorial  http://discuss.codechef.com/problems/CHEFLAND 
Tags  bridges, cook71, graph, kingofnumbers, mediumhard 
Date Added:  13062016 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 6.3, CPP14, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYPY, PYTH, PYTH 3.5, RUBY, SCALA, SCM chicken, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 