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.
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 "YES" (without quotes) if it possible to make all pairs of node good by adding at most one edge. Output "NO" (without quotes) otherwise.
- 1 ≤ N ≤ 105
- 0 ≤ M ≤ 2 * 105
- 1 ≤ x, y ≤ N
- It is guaranteed that the graph is connected.
- The given graph may contain multi-edges. It doesn't contain any self loops.
Input: 4 4 3 2 3 1 2 1 1 4 Output: YES
We can connect nodes 3 and 4 via an edge. After that all the pair of vertices will be good.
|Tags||bridges, cook71, graph, kingofnumbers, medium-hard|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.