小 Z 搭建了一个分流器系统：
该分流器系统总共包含 $n + 1$ 个节点，依次编号为 $1 \sim n+1$。除了节点 $1$ 之外，其余所有的节点均包含至少一个入度。除了节点 $n+1$, 其余所有的节点均包含恰好两个出度。同时，假定节点 $i$ 的出边连向的节点为 $out_{i, 0}, out_{i, 1}$, 则小 Z 保证 $i < out_{i, 0}, out_{i, 1} \le n+1$。不难发现，在上述条件下，整个分流器可以视为一张有向无环图。
分流器中的 $1 \sim n$ 节点的作用是将输入的物品，交替分发到节点 $out_{i, 0}, out_{i, 1}$ 上，来尽量使得每个节点的负载均衡。节点 $n+1$ 会收集其余分流器的信息，并将物品输出到下一个环节。为了实现交替分发的过程，$i$ 号分流器包含一个布尔变量 $b_i$，来实现物体的交替分发。
当节点 $1$ 输入一个物品的时候，整个分流器会按照如下的规则运作：
- 假定当前物品位于分流器节点 $p$.
- 如果 $p = n + 1$，物品离开分流器，运作结束
- 记录 $q = b_p$
- $b_p \leftarrow \neg b_p$(变为非 $b_p$)
- $p = out_{p, q}$
- 返回 step 1
在上一个物品未离开分流器的时候，下一个物品不会被投入；也就是说，小 Z 不需要考虑分流器同时存在多个物品的情况。
分流器的运作非常枯燥，因此小 Z 想到了这么一个问题：
- 假定 $S_T = \{b_i\}_{i=1}^n$ 记录了放入 $T$ 个物品后分流器 $1 \sim n$ 号节点的对应的布尔变量状态序列。初始状态被记作 $S_0$。
- 询问最小的正整数 $T$，使得 $S_T = S_0$，或者返回不存在这样的 $T$。
Input
第一行一个整数，表示 $n$。
接下来 $n$ 行，每行两个非负整数 $out_{i, 0}, out_{i, 1}$.
接下来一行 $n$ 个 0/1 变量，第 $i$ 个表示没有加入物品时候, $i$ 号节点所对应的布尔变量 $b_i$。
Output
一行一个数字，表示最小的正整数 $T$，使得 $S_T = S_0$，
如果不存在这样的 $T$, 输出 $-1$。
提示：输出有可能会非常大，记得使用高精度类型的结构存储！
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
Scoring
对于所有数据，$1 \le n \le 50\,000$。
Subtask1($5\%$) : $n \le 5$
Subtask2($15\%$) : $n \le 20$
Subtask3($15\%$) : 除了 $1$ 号与 $n + 1$ 号节点，其余节点入度均为 $1$。
Subtask4($20\%$) : $n \le 100$
Subtask5($20\%$) : $n \le 2000$
Subtask6($20\%$) : $b_i = 0$
Subtask7($5\%$) : $n \le 50000$