分数: 600 点
问题陈述
给你一个简单的无向图 N 顶点和 M 边,带有标记的顶点 1 to N 和边缘标记 1 to M。的 i第一条边连接顶点 U_i 和 V_i。最初, G 不包含奇数周期。
Takahashi 和 Aoki 将使用此图玩游戏 G。青木先行,他们轮流执行以下操作:
- 选择一对整数 (i,j) 与 1 \leq i < j \leq N 满足以下两个条件,则添加一条连接顶点的边 i 和 j to G.
- G 尚无连接顶点的边 i 和 j.
- 添加连接顶点的边 i 和 j 不会创建奇数循环。
无法执行此操作的玩家失败,另一位玩家获胜。
当两名玩家都发挥最佳状态时确定谁获胜。
什么是奇数周期?
顶点序列 (v_0,v_1,\ldots,v_k) of G 称为奇循环:
- k 是奇数。
- v_0=v_k.
- 对于每个 1\leq i \leq k,有一条边连接 v_{i-1} 和 v_{i}.
约束
- 1 \leq N \leq 2\times 10^5
- 0 \leq M \leq 2\times 10^5
- 1 \leq U_i < V_i \leq N
- 给定的图形不包含奇数循环。
- 给定的图形不包含多边。
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N M U_1 V_1 U_2 V_2 \vdots U_M V_M
输出
如果 Aoki(第一个玩家)获胜,则打印 Aoki;否则,如果高桥(第二个玩家)获胜,则打印 Takahashi.
示例输入 1
4 3 1 2 2 3 3 4
示例输出 1
Aoki
如果青木(第一个玩家)添加边缘 (1,4),高桥(第二个玩家)无法移动。因此,青木获胜。
示例输入 2
4 2 1 2 3 4
示例输出 2
Takahashi
无论青木怎么打,高桥都会赢。
示例输入 3
9 5 2 9 2 3 4 6 5 7 1 8
示例输出 3
Aoki