#PQJ1455x7975. QOJ 1455_7975
QOJ 1455_7975
标题: coneyisland - Problem - QOJ.ac
The problem was used in the following contests:
对于一张图 G 定义如下游戏:
游戏在足够聪明的两人 Alice 和 Bob 之间进行。有一枚棋子,Alice 先在 G 上任意选择一个节点,并将棋子放在该节点上。然后 Bob 和 Alice 轮流把棋子沿着 G 中的边移动到任意一个相邻的并且棋子之前没有停留过的节点上。Bob 先手,不能移动者输。
对于一张 n 个点的无向图 G 和正整数 k,图 Gk 定义如下:
- Gk 包含 nk 个点,分别为 (1,1),(1,2),⋯,(1,n),(2,1),⋯,(2,n),⋯,(k,1),⋯,(k,n)。
- 对于 ∀i∈[1,k],(i,u),(i,v) 之间有一条无向边,当且仅当 G 中 u,v 之间有一条无向边。
- 对于 ∀i∈[1,k−1],u∈[1,n],(i,u),(i+1,u) 之间有一条无向边。
有一个 n 个点的森林,初始包含 m 条边。有 q 次操作,操作分为三种:
- 1 u v:在 u,v 之间连一条无向边。保证连完后依然是一个森林。
- 2 u v:删除 u,v 之间的无向边。保证操作时 (u,v) 之间有一条无向边。
- 3 u k:记 T 为森林中 u 所在的树,求在 Tk 上进行上述游戏的结果。
输入格式
第一行三个非负整数 n,m,q。
接下来 m 行,每行两个正整数 u,v,表示初始森林中 (u,v) 之间有一条无向边。
接下来 q 行,每行包含三个正整数,表示一次操作,格式如「题目描述」中所示。
输出格式
对于每个 3 操作,输出一行 Alice 或 Bob,表示游戏的胜者
样例
样例输入 0
6 4 5
1 3
2 3
4 5
4 6
3 1 114514
3 1 998244353
1 3 4
3 1 1
3 1 3
样例输出 0
Bob
Alice
Alice
Bob
样例 1∼10
见下发文件中 ex_coneyisland1∼10.in 以及 ex_coneyisland1∼10.ans。第 i 组样例满足第 i 个子任务的限制。
数据范围
本题使用捆绑测试,子任务信息如下:
子任务编号n≤q≤数据类型分值11002000A1422002000A313320002000C21045×1042×104C11155×1042×104C2136105105A3157105105B148105105B2792×1052×105B312102×1052×105C311
其中,数据类型包含两个参数,第一个为 A、B、C 之一,具体限制如下:
- A:保证只存在第三种操作。
- B:保证不存在第二种操作。
- C:无特殊限制。
第二个为 1、2、3 之一,具体限制如下:
- 1:保证 k=1。
- 2:保证所有第三种操作中的 k 相同。
- 3:无特殊限制。
对于 100% 的数据,保证 1≤n,q≤2×105,0≤m<n,1≤k≤109。