2014 Mock CCC by Alex and Timothy

Problem S4: Roadtrip Tracking

Alice heard that her secret love interest, Bob, is going on a roadtrip to visit his friend in another city. She decides to follow him along the way to see if the friend is actually romantically affiliated with Bob (in which case, the outcome is not going to be pretty). Alice does not know the route that Bob is going to take, so she has acquired a map of the country. In their country, there are N (1 ≤ N ≤ 40 000) cities conveniently labeled from 1 to N, and M (1 ≤ M ≤ 200 000) bidirectional roads that run between the cities. There is at most one road between any pair of cities.

Both of them are currently in city 1, and Bob would like to go to city N. Alice also wants to get to city N eventually, but how she gets there does not matter. Bob's route will never return to the same city twice, and Alice does not plan to waste time by returning to the same city in her route either. The problem is, Alice cannot take the exact same route as Bob because Bob might get suspicious of a car that's following him for the entire trip. At some point, Alice will have to split up with Bob for a while. Alice needs to know whether there are at least two distinct ways to get from city 1 to city N.

Scoring

In addition to the constraints above, the following will hold:

• For test cases worth 5/15 of the points, N ≤ 10, M ≤ 20.
• For test cases worth 10/15 of the points, N ≤ 1 000, M ≤ 10 000.

Input Format

Line 1 contains the two integers N and M, denoting the number of cities and roads in their country.
The next M lines each contain two integers, a and b, indicating that there is a two-way road between city a and city b.

Output Format

Output "Yes" if there are at least two different ways to get from city 1 to city N without revisiting the same city twice, otherwise "No".

Sample Input

6 6
1 2
2 3
2 4
3 5
4 5
5 6

Sample Output

Yes

Explanation

Under the conditions above, there are exactly two ways to get from city 1 to city 6 — either by taking the path 1→2→3→5→6 or the path 1→2→4→5→6.

All Submissions
Best Solutions

Point Value: 15 (partial)
Time Limit: 2.00s
Memory Limit: 16M
Added: Feb 27, 2014
Author: Alex

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)