G. Nim Game In Byteland
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

There are $$$n$$$ cities, numbered from $$$1$$$ to $$$n$$$. City $$$1$$$ is where Alice lives, and city $$$n$$$ is where her rival Bob resides.

The cities are connected by directed roads. Each city has at most two outgoing roads.

Alice wants to move from city $$$1$$$ to city $$$n$$$. She can visit the same city multiple times. In each city she visits, she can choose to buy the pile in that city, but she can buy at most one pile per city during her journey.

When Alice reaches city $$$n$$$, she will play a Nim game against Bob using the piles she has collected. Bob plays first.

Your task is to determine whether Alice can select piles along her journey such that she guarantees a victory over Bob.

Note: Alice must select at least one pile on the path from $$$1$$$ to $$$n$$$, and it's guaranteed there's a path from $$$1$$$ to $$$n$$$.

In Nim, players take turns removing any number of stones from one pile. The player who removes the last stone wins.

Input

The first line contains an integer $$$n$$$ ($$$1 \leq n \leq 10^5$$$) — the number of cities.

Each of the next $$$n$$$ lines contains two integers $$$u_i$$$ and $$$v_i$$$ ($$$0 \leq u_i, v_i \leq n$$$) — the outgoing roads from city $$$i$$$.

  • If a city has one outgoing road, the second number will be $$$0$$$.
  • If a city has no outgoing roads, both numbers will be $$$0$$$.

The next line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \leq a_i \leq 10^6$$$) — the number of stones in the pile at each city.

Output

output YES if Alice can guarantee a win, and NO otherwise.

Examples
Input
4
2 0
3 4
1 0
0 0
2 4 1 1
Output
YES
Input
4
2 0
3 4
1 0
0 0
2 4 8 1
Output
NO