Problem E: Quick Answers
The Republic of Earthquakes is a country on an island in the Pacific
Ocean. Unfortunately, earthquakes occur regularly and some are very
destructive. So, there is a department specially prepared to assist
the population, where decisions such as which resources are moved from
a location to another are taken with utmost speed. The problem is
that, immediately after an earthquake, the information about the
damages is vague. For instance, they usually know how many roads are
no longer passable much before they can identify them. Nevertheless,
quick answers are needed.
All roads have two directions. Besides, before an earthquake, there
is at least one path between any two locations. Given the number of
roads that have been destroyed (in both directions) and two distinct
locations, your task is to determine whether or not there must still
be a path between the locations.
Let us see an example
with the four locations and the five roads depicted in the figure above.
When an earthquake destroys two roads:
-
Whichever the destroyed roads are,
there has to be a path between x and w.
- There may or may not be a path between x and y.
If, for instance, the destroyed roads are (x,y) and (x,z),
the path x w y exists.
But there is no path between x and y
when roads (x,y) and (y,w) are the not passable ones.
Task
Given the set of locations, the set of roads, the number of roads
destroyed by the earthquake, and two distinct locations, the goal is
to find out whether or not there must be a path between the latter.
Input
The first line of the input has two integers: L and
R. L is the number of locations and R is
the number of roads. Locations are identified by integers, ranging
from 0 to L−1. Each of the following R lines
contains two distinct integers, l1 and l2, which indicate that
there is a road between locations l1 and l2.
The last line has three integers,
D, l′ and l″,
which represent the question:
When an earthquake destroys D roads,
must there still be a path between locations l′ and l″?
Integers in the same line are separated by a single space.
Output
The output has a single line with the word
Yes,
if there must still be a path between the locations,
or No,
otherwise.
Constraints
| 2 ≤ L ≤ 2,500 | Number of locations |
| 1 ≤ R ≤ 10,000 | Number of roads |
| 1 ≤ D ≤ R | Number of destroyed roads |
Input example 1
4 5
0 1
0 3
2 0
1 2
2 3
2 0 2
Output example 1
Yes
Input example 2
7 9
0 2
0 3
5 0
4 1
3 5
3 4
5 2
6 4
1 6
1 6 2
Output example 2
No
MIUP'2012, 20 de Outubro, DCC/FCUP
This document was translated from LATEX by
HEVEA.