Santa and Pipes

View as PDF

Submit solution

Points: 5
Time limit: 2.0s
Memory limit: 64M

Problem type

Contrary to popular belief, Santa actually uses the sewer system under the city to deliver presents (he's much too big to fit in the chimneys). To do so, he has to travel through N sewer tunnels numbered 1 to N using M one-way pipes to get to each possible house.

On Christmas Eve, Santa will start at tunnel 1. Since he doesn't know what houses he must go to yet, Santa wants you to figure out if it's possible to travel to every tunnel from the one that he starts at.

Input Specification

The first line of input will contain two space-separated integers, N (2 \le N \le 10^4) and M (1 \le M \le 10^5).

The next M lines will each contain two space-separated integers, a_i and b_i (1 \le a_i, b_i \le N, a_i \ne b_i), the start and end tunnels for each pipe. There may be multiple pipes connecting the same pair of tunnels.

Output Specification

Output YES if Santa can travel to any tunnel from tunnel 1 and NO otherwise.

Sample Input 1

5 4
1 2
1 3
3 5
2 4

Sample Output 1


Explanation for Sample Output 1

You can reach tunnels 2 and 3 directly from tunnel 1. You can reach tunnels 4 and 5 from tunnels 2 and 3 respectively.

Sample Input 2

3 2
1 2
3 2

Sample Output 2


Explanation for Sample Output 2

You can't reach tunnel 3 by taking any sequence of pipes (recall that pipes are one-way).


There are no comments at the moment.