Alice 和 Bob 又打算玩游戏了。
有一个点数为 n 的有向无环图(点从 1 开始编号),每个点要么是黑点,要么是白点。图中可能有重边,每个点的出边是有序的。
有一段 DFS 程序,其伪代码如下:
定义过程 dfs(u):
if u 是白点
按顺序遍历 u 的所有出边 (u,v)
读取一个布尔值 g
if g
dfs(v)
else
按顺序遍历 u 的所有出边 (u,v)
dfs(v)
读取一个整数 r
dfs(r)
这段程序还有一个特殊性质:程序会在每次 dfs
过程调用开始前自动暂停。
Alice 和 Bob 启动了 k 个这样的程序,并给所有程序分别输入了一个点的编号作为 r(不同程序输入的 r 可能不同)。现在,这些程序都在读取 r 之后,调用 dfs(r)
之前暂停。
然后游戏开始。由 Alice 先手,双方轮流进行以下操作:
- 选择一个尚未结束执行的程序,将其从暂停中恢复。继续执行该程序,直到它再次暂停或结束。在这个过程中,该程序每次读取 g,当前玩家都可以选择读取结果是
true
还是false
。
每个程序都会在有限次暂停后结束,最终所有程序均会结束执行。如果轮到一名玩家操作时所有程序均已结束执行,该玩家输掉游戏,另一名玩家获胜。
双方都会采取最优策略。谁能获胜?
输入格式
第一行,一个正整数 n,表示图的点数。
第二行,n 个整数 c1,c2,…,cn,表示每个点的颜色。cu=0 表示 u 是黑点,cu=1 表示 u 是白点。
接下来 n 行描述图中的边,其中第 i 行有一个非负整数 mi 和 mi 个正整数 ei,1,ei,2,…,ei,mi,分别表示 i 的出边数量和各出边的终点。为了方便,保证对于所有 1≤i≤n,1≤j≤mi,有 ei,j>i;即 1,2,…,n 是该图的一个拓扑序。
接下来一行,一个正整数 k,表示程序数量。
最后一行,k 个正整数 r1,r2,…,rk,分别表示游戏开始前各程序的输入。
输出格式
一行,一个字符串,表示获胜者。如果 Alice 获胜,输出 Alice
;如果 Bob 获胜,输出 Bob
。
样例一
input
4
1 0 1 0
1 2
2 4 3
1 4
0
1
2
output
Alice
explanation
该图有 4 个点。
- 点 1:白色,一条出边,终点为 2;
- 点 2:黑色,两条出边,终点分别为 4、3;
- 点 3:白色,一条出边,终点为 4;
- 点 4:黑色,没有出边。
只有一个程序,其初始点为点 2。以下为双方采取最优策略时该程序的执行过程:
- 输入初始点 r=2 并暂停执行。游戏开始,接下来轮到 Alice。因为只有一个程序,双方总是只能选择这个程序。Alice 选择继续执行该程序。
- dfs(2)
- 暂停执行。轮到 Bob。Bob 选择继续执行该程序。
- dfs(4)
- 过程返回
- 暂停执行。轮到 Alice。Alice 选择继续执行该程序。
- dfs(3)
- 读取一个布尔值 g。Alice 选择
false
。 - 过程返回
- 读取一个布尔值 g。Alice 选择
- 过程返回
- 结束执行。轮到 Bob。
轮到 Bob 时所有程序均已结束执行,Bob 输掉游戏,Alice 获胜。
在该样例中,点 1 存在与否实际上对游戏过程没有影响。
另外,如果 Alice 在 dfs(3) 中选择 true
,那么接下来 dfs(3) 会调用 dfs(4),并在调用前多暂停一次。这会导致结束执行时轮到 Alice,获胜者会变成 Bob。由于双方均采取最优策略,这样的事情不会发生。
样例二
input
5
1 1 0 0 1
2 3 5
2 3 5
2 5 4
0
0
2
1 2
output
Bob
explanation
两个程序的初始点分别为 1 和 2,而点 1 和 2 的颜色、出边完全一致,只有编号不同。
Bob 可以采取以下策略:当 Alice 选择执行某个程序后,Bob 选择执行另一个程序并给出相同的输入。容易证明这是 Bob 的必胜策略。
样例三
input
10
0 0 0 0 1 1 1 1 0 1
1 2
2 3 4
0
3 5 8 10
1 6
1 7
0
1 9
0
0
1
1
output
Bob
数据范围
对于所有数据:
- 1≤n≤2×105
- ci∈{0,1}(对于所有 1≤i≤n)
- 0≤mi≤4×105(对于所有 1≤i≤n)
- ∑ni=1mi≤4×105
- i<ei,j≤n(对于所有 1≤i≤n,1≤j≤mi)
- 1≤k≤2×105
- 1≤ri≤n(对于所有 1≤i≤k)
子任务 | 分值 | 特殊限制 |
---|---|---|
1 | 5 | ci=0(对于所有 1≤i≤n) |
2 | 15 | k=1,r1=1 |
3 | 15 | n≤10,∑ni=1mi≤10,k≤10 |
4 | 20 | ci=1(对于所有 1≤i≤n);对于每个点 u,只有至多一条边的终点为 u;对于所有 1≤i≤k,图中不存在终点为 ri 的边 |
5 | 20 | ci=1(对于所有 1≤i≤n) |
6 | 25 | 没有额外的约束条件 |
时间限制:2s
空间限制:256MB