#PQJ1455x7975. QOJ 1455_7975

    ID: 2612 传统题 2000ms 512MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:集训队赛事:2023-2024 集训队互测并查集拓扑排序

QOJ 1455_7975

标题: coneyisland - Problem - QOJ.ac

Statistics

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。