Castle Connection

You are given n castles numbered from 1 to n and a list of bidirectional roads connecting them. Some roads may have been destroyed due to an attack. Your task is to determine whether it is still possible to travel from castle 1 to a given castle k (with 2 ≤ k ≤ n) using only the remaining roads.

The input will specify the number of castles, the target castle k, a list of all roads, and a list of the roads that have been destroyed. A road, if not destroyed, allows travel in both directions. The answer is YES if there is a path from castle 1 to castle k using only the intact roads, and NO otherwise.

Note: All roads are undirected, and if a road appears in the destroyed list, it is removed from both directions.

inputFormat

The input is given via standard input (stdin) with the following format:

n k
m
u1 v1
...
um vm
d
x1 y1
...
xd yd

Here,

• n and k are two integers denoting the number of castles and the target castle respectively.
• m is the number of roads followed by m lines each containing two integers u and v representing a road between castle u and castle v.
• d is the number of destroyed roads followed by d lines each containing two integers representing a destroyed road.

outputFormat

Output a single line to standard output (stdout) with either YES if there is a path from castle 1 to castle k using only the remaining roads, or NO if no such path exists.

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

YES