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:


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.


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.


The output has a single line with the word Yes, if there must still be a path between the locations, or No, otherwise.


2 ≤ L ≤ 2,500Number of locations
1 ≤ R ≤ 10,000Number of roads
1 ≤ DRNumber of destroyed roads

Input example 1

4 5
0 1
0 3
2 0
1 2
2 3
2 0 2

Output example 1


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



MIUP'2012, 20 de Outubro, DCC/FCUP

This document was translated from LATEX by HEVEA.