QOJ.ac

QOJ

Time Limit: 2 s Memory Limit: 512 MB Total points: 100

# 7975. coneyisland

统计

对于一张图 $ G $ 定义如下游戏:

游戏在足够聪明的两人 Alice 和 Bob 之间进行。有一枚棋子,Alice 先在 $ G $ 上任意选择一个节点,并将棋子放在该节点上。然后 Bob 和 Alice 轮流把棋子沿着 $ G $ 中的边移动到任意一个相邻的并且棋子之前没有停留过的节点上。Bob 先手,不能移动者输。

对于一张 $ n $ 个点的无向图 $ G $ 和正整数 $ k $,图 $ G^k $ 定义如下:

  • $ G^k $ 包含 $ nk $ 个点,分别为 $ (1, 1), (1, 2), \cdots, (1, n), (2, 1), \cdots, (2, n), \cdots, (k, 1), \cdots, (k, n) $。
  • 对于 $ \forall i \in [1, k] $,$ (i, u), (i, v) $ 之间有一条无向边,当且仅当 $ G $ 中 $ u, v $ 之间有一条无向边。
  • 对于 $ \forall i \in [1, k - 1], u \in [1, n] $,$ (i, u), (i + 1, u) $ 之间有一条无向边。

有一个 $ n $ 个点的森林,初始包含 $ m $ 条边。有 $ q $ 次操作,操作分为三种:

  • $ \texttt{1 u v} $:在 $ u, v $ 之间连一条无向边。保证连完后依然是一个森林。
  • $ \texttt{2 u v} $:删除 $ u, v $ 之间的无向边。保证操作时 $ (u, v) $ 之间有一条无向边。
  • $ \texttt{3 u k} $:记 $ T $ 为森林中 $ u $ 所在的树,求在 $ T^k $ 上进行上述游戏的结果。

输入格式

第一行三个非负整数 $ n, m, q $。

接下来 $ m $ 行,每行两个正整数 $ u, v $,表示初始森林中 $ (u, v) $ 之间有一条无向边。

接下来 $ q $ 行,每行包含三个正整数,表示一次操作,格式如「题目描述」中所示。

输出格式

对于每个 3 操作,输出一行 $ \texttt{Alice} $ 或 $ \texttt{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 \sim 10 $

见下发文件中 $ \boldsymbol{ex\_coneyisland1 \sim 10.in} $ 以及 $ \boldsymbol{ex\_coneyisland1 \sim 10.ans} $。第 $ i $ 组样例满足第 $ i $ 个子任务的限制。

数据范围

本题使用捆绑测试,子任务信息如下:

子任务编号$ n \le $$ q \le $数据类型分值
$ 1 $$ 100 $$ 2000 $A1$ 4 $
$ 2 $$ 200 $$ 2000 $A3$ 13 $
$ 3 $$ 2000 $$ 2000 $C2$ 10 $
$ 4 $$ 5 \times 10^4 $$ 2 \times 10^4 $C1$ 11 $
$ 5 $$ 5 \times 10^4 $$ 2 \times 10^4 $C2$ 13 $
$ 6 $$ 10^5 $$ 10^5 $A3$ 15 $
$ 7 $$ 10^5 $$ 10^5 $B1$ 4 $
$ 8 $$ 10^5 $$ 10^5 $B2$ 7 $
$ 9 $$ 2 \times 10^5 $$ 2 \times 10^5 $B3$ 12 $
$ 10 $$ 2 \times 10^5 $$ 2 \times 10^5 $C3$ 11 $

其中,数据类型包含两个参数,第一个为 A、B、C 之一,具体限制如下:

  • A:保证只存在第三种操作。
  • B:保证不存在第二种操作。
  • C:无特殊限制。

第二个为 1、2、3 之一,具体限制如下:

  • 1:保证 $ k = 1 $。
  • 2:保证所有第三种操作中的 $ k $ 相同。
  • 3:无特殊限制。

对于 $ 100\% $ 的数据,保证 $ 1 \le n, q \le 2 \times 10^5, 0 \le m < n, 1 \le k \le 10^9 $。