题意

有一张 $n$ 个点 $m$ 条边的图，保证一开始不存在奇环，Aoki 和 Takahashi 轮流在图上添加边，要求添加之后图任然不存在奇环，且不能有重边。无法操作者输。求最后谁会赢。

分析

这个问题要从奇偶性入手，因为不能有奇环，我们可以给原图黑白染色，然后分类讨论。

$n$ 为奇数

因为 $n$ 为奇数，那么在游戏结束的时候二分图两部分一定是一奇一偶，那么最终二分图上的边数就一定是偶数条。所以双方可以操作的边数就取决于一开始的边数，即 $m$ 的奇偶性。如果 $m$ 为奇数，那么就是 Aoki，否则就是 Takahashi。

$n$ 为偶数

$n$ 为偶数的情况比较多，我们先有如下定义。

• $cnt_{11}$ 表示二分图两部分都为奇数的连通块数量，我们称之为 A 类连通块。
• $cnt_{00}$ 表示二分图两部分都为偶数的连通块数量，我们称之为 B 类连通块。
• $cnt_{10}$ 表示二分图两部分一奇一偶且连通块内至少两个点的连通块数量，我们称之为 C 类连通块。
• $cnt_a$ 表示只有一个点的连通块数量。

并且显然，在双方都不改变图的连通性的前提下，结果就已经完全确定了，详见本场 E 题。所以双方会有限把各个连通块连接起来，变成一个连通块。而且容易发现，$cnt_{00}$ 不会对我们的答案产生任何影响。接下来我们分类讨论。

$cnt_{10} = 0$

先说结论，如果 $\frac{cnt_a}{2} + cnt_{11} + m$ 为奇数，那么就是 Aoki，否则是 Takahashi。我们下面称这个值为 $x$。

显而易见，这种情况下 $cnt_a$ 一定是偶数。我们考虑归纳证明。

如果当前局面 $x$ 为奇数，那么我们就可以把两个单点连接，会使得 $cnt_a$ 减去 $2$，那么 $x$ 变成偶数。或者连接两个 A 类连通块，那么就会少掉两个 A 类连通块，多一个 B 类连通块，$x$ 的奇偶性也会变。

接下来，对方一样会进行依次操作，让 $x$ 再便会奇数。但是对方也很聪明，可以把一个单点连接到一个 A 类连通块上，这样子就会使得 $cnt_{10}$ 变成 $1$，不在这种情况内。所以我们要把局面拉回 $cnt_{10}$ 变回来。因为 $cnt_a$ 一定是偶数，对方操作后，$cnt_a$ 会变成奇数，就一定会剩下一个单点。我们就可以把这个单点也连接到对方选择的 A 类连通块上，局面就会变回来，对方面对的仍然是 $x$ 为偶数。

初始情况就是所有数字都是 $0$，那么 $x$ 为 $0$，先手必输，所以如果 $x$ 为奇数，先手赢，否则后手赢。

$cnt_{10} = 1$

这种情况其实就是先手上面情况的子情况，这种情况一定是 Aoki。

具体的，因为这种情况 $cnt_a$ 是奇数，我们可以把一个单点和一个 C 类连通块连接，而且此时我们可以把这个 C 类连通块变成任意一个 A 类连通块或者 B 类连通块。因为我们希望我们操作之后 $x$ 为偶数，所以我们可以通过选择 A 类连通块或 B 类连通块来改变 $cnt_{11}$ 的奇偶性。所以无论如何，一定是 Aoki。

$cnt_{10} = 2$

这种情况，也一定是 Aoki。

我们这种情况内，$cnt_a$ 一定是偶数。我们一样的可以连接两个 C 类连通块，并且选择变成 A 类连通块还是 B 类连通块，可以变成 $cnt_{11} = 0$ 的情况，做到 $x$ i一定为偶数。

$cnt_{10} \ge 3$

最后这种情况，我们发现，因为一次操作最多减少两个 C 类连通块，而如果一个人使得局面变成了 $cnt_{11} \in [1,2]$ 的话，那个人就输了。所以局面一定会若干次操作之后变成三个连通块的情况，并且谁让局面变成只有三个连通块且无法在块内连接时，那个人就赢了。所以这就取决于一开始 $m$ 的奇偶性，如果 $m$ 为奇数，那么 Aoki，否则 Takahashi。

总结

最终我们整理出来了所有的情况。

• $n$ 为奇数，答案取决于 $m$ 的奇偶性。
• $n$ 为偶数，$cnt_{10} = 0$，答案取决于 $\frac{cnt_a}{2} + cnt_{11} + m$ 的奇偶性。
• $n$ 为偶数，$cnt_{10} \in [1,2]$，答案为 Aoki。
• $n$ 为偶数，$cnt_{10} \ge 3$，答案取决于 $m$ 的奇偶性。

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define il inline
#define N 200005
il ll rd(){
    ll s = 0, w = 1;
    char ch = getchar();
    for (;ch < '0' || ch > '9'; ch = getchar()) if (ch == '-') w = -1;
    for (;ch >= '0' && ch <= '9'; ch = getchar()) s = ((s << 1) + (s << 3) + ch - '0');
    return s * w;
}
int n = rd(), m = rd(), u, v, col[N], t[N][2], s0, s1, s2, cnt;
vector <int> e[N];
void dfs(int u, int d){
    col[u] = d, t[cnt][d]++;
    for (int v : e[u]) if (col[v] == -1) dfs(v, d ^ 1);
}
int main(){
    for (int i = 1; i <= n; i++) col[i] = -1; 
    for (int i = 1; i <= m; i++) u = rd(), v = rd(), e[u].push_back(v), e[v].push_back(u);
    if (n & 1) return 0 & puts((m & 1) ? "Aoki" : "Takahashi");
    for (int i = 1; i <= n; i++) if (col[i] == -1) cnt++, dfs(i, 0);
    for (int i = 1; i <= cnt; i++){
        if ((!t[i][0] && t[i][1] == 1) || (!t[i][1] && t[i][0] == 1)) s0++;
        else if ((t[i][0] & 1) && (t[i][1] & 1)) s1++;
        else if ((t[i][0] & 1) || (t[i][1] & 1)) s2++;
    }if (!s2) puts(((s0 / 2 + s1 + m) & 1) ? "Aoki" : "Takahashi");
    else if (s2 <= 2) puts("Aoki");
    else puts((m & 1) ? "Aoki" : "Takahashi");
    return 0;
}