Santa and Pipes

View as PDF

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

Author:
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 sewer tunnels numbered to using one-way pipes to get to each possible house.

On Christmas Eve, Santa will start at tunnel . 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, and .

The next lines will each contain two space-separated integers, and , 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 and NO otherwise.

Sample Input 1

5 4
1 2
1 3
3 5
2 4

Sample Output 1

YES

Explanation for Sample Output 1

You can reach tunnels and directly from tunnel . You can reach tunnels and from tunnels and respectively.

Sample Input 2

3 2
1 2
3 2

Sample Output 2

NO

Explanation for Sample Output 2

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