Once you confirm the aliens come in peace, your team finally relaxes. Communication becomes smoother, you apologise for trying to blow up their ship, and they apologise for kidnapping you in the first place! In space, you can never be too sure...

Before you part ways, you ask the aliens for help getting home. They hand you a Hyperdrive, their latest (experimental) technology.

To guide you, the aliens provide a stellar map:

• The galaxy consists of ~n~ stars, numbered from ~1~ to ~n~.
• TRAPPIST-1 is star ~1~ (your current location), and our Sun is star ~n~ (your destination).
• Each star has a directed connection to exactly one other star.

However, the Hyperdrive comes with limitations:

• At each star, you are allowed to "jump" to another star that is exactly ~d~ steps away in the connection graph, where ~d~ is chosen from a set of allowed distances for that star.
• You cannot jump more or fewer steps than allowed, only values from the given set may be used.

Is it possible to get home using the Hyperdrive?

Input

The first line consists of a single integer, ~n~ ~(2 \leq n \leq 500)~, the number of stars in the galaxy.

The next ~n~ lines consist of two integers ~a~ ~(1 \leq a \leq n)~ and ~b~ ~(1 \leq b \leq n)~, representing that star ~a~ and ~b~ are connected by one step.

The next line consists of a single integer, ~m~ ~(2 \leq m \leq 500)~, the number of possible jumps in the galaxy.

The next ~m~ lines consist of two integers ~a~ ~(1 \leq a \leq n)~ and ~d~ ~(1 \leq d \leq 10^9)~, indicating that you can jump exactly ~d~ steps from star ~a~.

Output

If it is possible to get to our sun (star ~n~) from TRAPPIST-1 (star ~1~), output "Yes". Otherwise, output "No".

Clarifications

• The graph is weakly connected.

Example

Input 1

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

Output 1

Yes

Starting from star ~1~, make ~6~ jumps. You will end up on star ~4~.

From star ~4~, make ~2~ jumps. You will end up on star ~6~.

Welcome home!

Input 2

3
1 2
2 3
3 1
2
1 1
2 2

Output 2

No

Input 3

5
1 5
5 2
2 3
3 1
4 5
4
1 2
1 3
2 8
3 3

Output 3

No