Little Z has built a splitter system:

The splitter system consists of a total of $n + 1$ nodes, numbered $1$ to $n+1$. Except for node $1$, all other nodes have an in-degree of at least $1$. Except for node $n+1$, all other nodes have exactly two out-degrees. Furthermore, assuming the outgoing edges of node $i$ point to nodes $out_{i, 0}$ and $out_{i, 1}$, Little Z guarantees that $i < out_{i, 0}, out_{i, 1} \le n+1$. It is not difficult to see that under these conditions, the entire splitter can be viewed as a directed acyclic graph.

The nodes $1 \sim n$ in the splitter serve to distribute incoming items alternately to nodes $out_{i, 0}$ and $out_{i, 1}$ to keep the load on each node as balanced as possible. Node $n+1$ collects information from the rest of the splitter and outputs the items to the next stage. To implement the alternating distribution process, splitter $i$ contains a boolean variable $b_i$.

When an item is input into node $1$, the entire splitter operates according to the following rules:

1. Assume the current item is at splitter node $p$.
2. If $p = n + 1$, the item leaves the splitter, and the operation ends.
3. Record $q = b_p$.
4. $b_p \leftarrow \neg b_p$ (flip $b_p$).
5. $p = out_{p, q}$.
6. Return to step 1.

The next item is not input until the previous item has left the splitter; that is, Little Z does not need to consider the case where multiple items exist in the splitter simultaneously.

The operation of the splitter is very monotonous, so Little Z thought of the following problem:

• Let $S_T = \{b_i\}_{i=1}^n$ record the state sequence of the boolean variables for nodes $1 \sim n$ after $T$ items have been inserted. The initial state is denoted as $S_0$.
• Find the smallest positive integer $T$ such that $S_T = S_0$, or return that no such $T$ exists.

Input

The first line contains an integer $n$.

The next $n$ lines each contain two non-negative integers $out_{i, 0}, out_{i, 1}$.

The next line contains $n$ 0/1 variables, where the $i$-th variable represents the initial state of the boolean variable $b_i$ for node $i$ before any items are added.

Output

Output a single integer representing the smallest positive integer $T$ such that $S_T = S_0$.

If no such $T$ exists, output $-1$.

Note: The output may be very large; remember to use a big integer structure to store it!

Examples

Input 1

5
2 3
4 5
4 5
5 6
6 6
0 0 0 0 0

Output 1

8

Input 2

5
2 3
4 5
4 5
6 6
6 6
0 0 0 0 0

Output 2

4

Subtasks

For all data, $1 \le n \le 50\,000$.

Subtask 1 ($5\%$): $n \le 5$

Subtask 2 ($15\%$): $n \le 20$

Subtask 3 ($15\%$): Except for node $1$ and node $n + 1$, all other nodes have an in-degree of $1$.

Subtask 4 ($20\%$): $n \le 100$

Subtask 5 ($20\%$): $n \le 2000$

Subtask 6 ($20\%$): $b_i = 0$

Subtask 7 ($5\%$): $n \le 50000$