DMOPC '18 Contest 6 P3 - Wish Upon a Star - Olympiads Online Judge

DMOPC '18 Contest 6 P3 - Wish Upon a Star

Points: 10 (partial)

Time limit: 1.0s

Java 2.5s

Python 2.5s

Memory limit: 256M

Author:

Kirito

Problem type

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 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?

Constraints

Subtask 1 [20%]

$1 \le N, M \le 5\,000$ ~1 \le N, M \le 5\,000~

Subtask 2 [80%]

$1 \le N, M \le 200\,000$ ~1 \le N, M \le 200\,000~

Input Specification

The first line of input will contain two space separated integers, $N$ ~N~ and $M$ ~M~, the number of nodes and edges, respectively.
The next $M$ ~M~ lines will each contain two space separated integers, $a_i$ ~a_i~ and $b_i$ ~b_i~, indicating there exists a bidirectional edge from $a_i$ ~a_i~ to $b_i$ ~b_i~.

Output Specification

Output YES if the graph can be restored to a forest by removing at most one edge, and NO otherwise.

Sample Input 1

Sample Output 1

YES

Explanation for Sample Output 1

Removing the edge $2 \to 3$ ~2 \to 3~ makes the graph a forest.

Sample Input 2

4 2
1 2
3 4

Sample Output 2

YES

Explanation for Sample Output 2

The graph is already a forest.

Comments

-6

jordan commented on Aug. 19, 2020, 9:21 p.m.

Lol overlord

This comment is hidden due to too much negative feedback. Show it anyway.