Quantum Superposition

Through quantum superposition, you are in two universes at the same time. Each universe can be represented as a directed acyclic graph. You begin at the start vertices in each universe and your goal is to reach the end vertices. Now, you are wondering, can you reach the end vertices in both universes where the sum of steps made in each universe is exactly equal to a given number?

The first line contains $1 \leq N_1, N_2 \leq 1\, 000$, the number of vertices in each universe, and $0 \leq M_1, M_2 \leq 2\, 000$, the number of edges in each universe. In both universes, vertex $1$ is the start vertex. Vertices $N_1$ and $N_2$ are the end vertices in each respective universe.

Each of the next $M_1$ lines contains two numbers $1 \leq u, v \leq N_1$, indicating a directed edge from vertex $u$ to vertex $v$ in universe 1.

Each of the next $M_2$ lines contains two numbers $1 \leq u, v \leq N_2$, indicating a directed edge from vertex $u$ to vertex $v$ in universe 2.

There will not be duplicate edges. It is guaranteed that the universes are acyclic, and there exists a path from start to end vertex in each universe.

The next line contains $1 \leq Q \leq 2\, 000$, the number of queries. Each query consists of a line with a single integer $0 \leq q \leq 2\, 000$ that is the sum of steps made in each universe.

For each query, output “Yes” if it is possible to reach the end vertices in both universes where the sum of steps made in each universe is exactly equal to the given query, or “No” otherwise.

Sample Input 1 | Sample Output 1 |
---|---|

3 2 3 1 1 2 1 3 2 3 1 2 5 0 1 2 3 4 |
No No Yes Yes No |