2014 Mock CCC by Alex and Timothy
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
cities conveniently labeled from
to
, and
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 , and Bob would like to go to city
. Alice also wants to get to city
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
to city
.
Scoring
In addition to the constraints above, the following will hold:
- For test cases worth
of the points,
.
- For test cases worth
of the points,
.
Input Specification
Line contains the two integers
and
, denoting the number of
cities and roads in their country.
The next lines each contain two integers,
and
, indicating
that there is a two-way road between city
and city
.
Output Specification
Output Yes
if there are at least two different ways to get from city
to city
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
to city
— either by taking the path
or the path
.
Comments