Path Existence: Avoid Closed Cities and Roads

You are given an undirected graph with n cities and r bidirectional roads. Some cities and roads are closed. Your task is to determine whether there is a valid path from a starting city a to a destination city b such that the path does not pass through any closed city and does not use any closed road.

Details:

• The graph is represented as \(G=(V,E)\), where \(V\) is the set of n cities and \(E\) is the set of r roads.
• Certain cities are closed. Let \(C \subseteq V\) be the set of closed cities.
• Certain roads are closed. A road between cities \(u\) and \(v\) is considered closed if \((u,v)\) (or equivalently \((v,u)\)) belongs to the set of closed roads \(R_c\).
• You are required to avoid traversing any city in \(C\) and any road in \(R_c\).

Determine if there exists a path from a to b under these conditions. Print YES if such a path exists, and NO otherwise.

inputFormat

The input is given from the standard input (stdin) as follows:

1. The first line contains four space-separated integers: \(n\), \(r\), \(c\), and \(cr\), where \(n\) is the number of cities, \(r\) is the number of roads, \(c\) is the number of closed cities, and \(cr\) is the number of closed roads.
2. The next \(r\) lines each contain two space-separated integers \(u\) and \(v\), representing a bidirectional road between cities \(u\) and \(v\).
3. The following line contains two space-separated integers \(a\) and \(b\): the starting city and the destination city.
4. If \(c > 0\), the next line contains \(c\) space-separated integers indicating the closed cities. If \(c = 0\), this line is omitted.
5. If \(cr > 0\), the next \(cr\) lines each contain two space-separated integers denoting a closed road between two cities. If \(cr = 0\), these lines are omitted.

It is guaranteed that the input follows this format.

outputFormat

Output a single line to the standard output (stdout) containing YES if there exists a valid path from city a to city b under the given constraints, or NO otherwise.

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

YES