QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 768 MB Total points: 100 Hackable ✓
[-36]

# 8671. 分流器

Statistics

小 Z 搭建了一个分流器系统:

该分流器系统总共包含 n+1 个节点,依次编号为 1n+1。除了节点 1 之外,其余所有的节点均包含至少一个入度。除了节点 n+1, 其余所有的节点均包含恰好两个出度。同时,假定节点 i 的出边连向的节点为 outi,0,outi,1, 则小 Z 保证 i<outi,0,outi,1n+1。不难发现,在上述条件下,整个分流器可以视为一张有向无环图。

分流器中的 1n 节点的作用是将输入的物品,交替分发到节点 outi,0,outi,1 上,来尽量使得每个节点的负载均衡。节点 n+1 会收集其余分流器的信息,并将物品输出到下一个环节。为了实现交替分发的过程,i 号分流器包含一个布尔变量 bi,来实现物体的交替分发。

当节点 1 输入一个物品的时候,整个分流器会按照如下的规则运作:

  1. 假定当前物品位于分流器节点 p.
  2. 如果 p=n+1,物品离开分流器,运作结束
  3. 记录 q=bp
  4. bp¬bp(变为非 bp)
  5. p=outp,q
  6. 返回 step 1

在上一个物品未离开分流器的时候,下一个物品不会被投入;也就是说,小 Z 不需要考虑分流器同时存在多个物品的情况。

分流器的运作非常枯燥,因此小 Z 想到了这么一个问题:

  • 假定 ST={bi}ni=1 记录了放入 T 个物品后分流器 1n 号节点的对应的布尔变量状态序列。初始状态被记作 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

对于所有数据,1n50000

Subtask1(5%) : n5

Subtask2(15%) : n20

Subtask3(15%) : 除了 1 号与 n+1 号节点,其余节点入度均为 1

Subtask4(20%) : n100

Subtask5(20%) : n2000

Subtask6(20%) : bi=0

Subtask7(5%) : n50000