← 返回题目列表

AtCoder · abc398_g

G. 不仅仅是树游戏

中文机器翻译题面 查看原题

分数: 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