AT_abc398_g.[ABC398G] Not Only Tree Game

给定一个简单无向图 $G$，包含 $N$ 个顶点和 $M$ 条边，顶点编号为 $1$ 到 $N$，边编号为 $1$ 到 $M$。其中第 $i$ 条边连接顶点 $U_i$ 和 $V_i$。初始时，$G$ 中不包含奇闭路。

青木君和高桥君将使用这个图 $G$ 进行游戏。两人轮流执行以下操作（青木君为先手）：

• 选择满足 $1 \leq i < j \leq N$ 的整数对 $(i, j)$，且满足以下两个条件：

  • $G$ 当前不包含连接顶点 $i$ 和顶点 $j$ 的边；
  • 在 $G$ 中添加连接顶点 $i$ 和顶点 $j$ 的边后，$G$ 仍然不形成奇闭路；

  然后，将这条边添加到 $G$ 中。

无法进行操作的一方判负，另一方获胜。请判断在双方采取最优策略的情况下，哪一方会获胜。

奇环的定义：当且仅当顶点序列 $(v_0, v_1, \ldots, v_k)$ 满足以下所有条件时，称该序列为奇环：

• $k$ 是奇数；
• $v_0 = v_k$；
• 对于所有 $1 \leq i \leq k$，存在连接顶点 $v_{i-1}$ 和 $v_i$ 的边。

输入通过标准输入给出，格式如下：

$N$ $M$
$U_1$ $V_1$
$U_2$ $V_2$
$\vdots$
$U_M$ $V_M$

如果先手青木君获胜，输出 Aoki；如果后手高桥君获胜，输出 Takahashi。

约束条件

• $1 \leq N \leq 2 \times 10^5$
• $0 \leq M \leq 2 \times 10^5$
• $1 \leq U_i < V_i \leq N$
• 给定的图 $G$ 不包含奇闭路；
• 给定的图 $G$ 不存在多重边；
• 输入均为整数。

样例解释 1

先手青木君选择 $(1, 4)$ 添加边后，后手高桥君无法进行任何操作，因此青木君获胜。

样例解释 2

无论青木君如何操作，高桥君都将获胜。

翻译由 DeepSeek R1 完成