#C5956. Blocked Road Navigation
Blocked Road Navigation
Blocked Road Navigation
You are given a network with N locations and M bidirectional roads connecting them. Some roads are temporarily blocked. For each dataset, you are provided with:
- A line containing two integers N and M, representing the number of locations and roads, respectively.
- A line with a list of space‐separated road indices (1-indexed) that are blocked. These roads should be ignored.
- A line with two integers A and B indicating the starting and destination locations.
- M subsequent lines, each containing two integers si and ti that represent a road connecting locations si and ti.
Your task is to determine whether there is a path from location A to location B using only the roads that are not blocked. The input may contain several test datasets. The end of input is signified by a line containing "0 0".
Note: All formulas are in LaTeX format. For example, the number of locations is denoted by $N$, the number of roads by $M$, and the road endpoints by $(s_i, t_i)$.
inputFormat
The input consists of one or more datasets. Each dataset is formatted as follows:
- A line containing two integers,
N M
. - A line containing the list of blocked road indices (space-separated). If no roads are blocked, this line will be empty.
- A line containing two integers,
A B
, whereA
is the starting location andB
is the destination. M
lines follow; each line contains two integers,si ti
, representing a road connecting locations $s_i$ and $t_i$.
The input terminates with a line containing 0 0
, which should not be processed.
outputFormat
For each dataset, output a single line containing either YES
if there exists a path from location A
to location B
using only non-blocked roads, or NO
otherwise.
5 6
1 3
1 5
1 2
2 3
3 4
4 5
5 1
4 2
0 0
YES
</p>