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