DMOPC '18 Contest 6 P3 - Wish Upon a Star

View as PDF

Submit solution

Points: 10 (partial)
Time limit: 1.0s
Java 2.5s
Python 2.5s
Memory limit: 256M

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?


Subtask 1 [20%]

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

Subtask 2 [80%]

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

Input Specification

The first line of input will contain two space separated integers, N and M, the number of nodes and edges, 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.

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

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.


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

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