Is There a Route

Difficulty: 1200 4000 ms 128 MB

graphs

Given the network and two people S and T, are they connected by some chain of links?

Input: the first line has N and M; each of the next M lines has an edge u v (1-based). The last line has S and T.

Output: YES or NO.

Constraints:

• 1 ≤ N ≤ 10⁴
• 0 ≤ M ≤ 2×10⁴
• multiple edges and self-loops may appear

Sample Tests

4 2
1 2
3 4
1 4

NO

4 3
1 2
2 3
3 4
1 4

YES

Read the Editorial