Hide

Problem C
Sky Islands

/problems/skyislands/file/statement/en/img-0001.png
a single skyisland

Alex wants to build a sky base consisting of $N$ sky islands, numbered $1, \ldots , N$. There are a total of $M$ bridges, directly connecting certain islands to others. Because she does not have an elytra (wings that enable players to fly) and cannot fly, she needs to make sure that there exists a way for her to travel from one island to any other island. It is fine if she needs to travel through other islands to get to the destination. We call her islands connected if it exhibits such property. Note: a single island is always connected.

Given the number of islands $N$ and all the bridges $b_1, \cdots , b_ M$, would you be able to determine whether Alex’s islands are connected?

Input

The first line of input consists of two space-separated integers, $1 \leq N \leq 900$ and $0 \leq M \leq 10^6$, representing the number of islands and the number of bridges respectively. The following $M$ lines each consist of two space-separated integers $1 \leq a, b \leq N$, representing a bridge between island $a$ and island $b$.

Output

Output “YES” if all of Alex’s islands are connected. Output “NO” otherwise.

Sample Input 1 Sample Output 1
4 3
1 2
2 3
3 4
YES
Sample Input 2 Sample Output 2
4 4
1 2
2 3
3 4
4 1
YES
Sample Input 3 Sample Output 3
4 3
1 2
2 1
3 4
NO
CPU Time limit 6 seconds
Memory limit 1024 MB
Author
Tony Xia
Source CodeSprint LA 2021
License Creative Commons License (cc by-sa)

Please log in to submit a solution to this problem

Log in