前言
赛时机房大佬们以及标算都用 SG 函数做的，而我用的是最朴素的大力分类讨论，wa 了十二发才过，写下这篇题解记录我的想法，纪念一下这场比赛。
题目简意
\(N\) 个格子排成一排，中间有 \(M\) 个格子的颜色易知，第 \(X_i\) 个格子的颜色是 \(Y_i(Y_i\in \{0,1\})\) 。现在 Takahashi 和 Aoki 玩一个游戏，双方轮流选择一个颜色未知的格子，给它染色，需要保证该格子和其相邻的格子颜色不同。 Takahashi 先手，谁不能操作就输了，双方均采用最优策略，问最后谁获胜。\(N\le 10^{18}，\forall 1\le i<n,X_i<X_{i+1},X_{i}+1=X_{i+1}\Longrightarrow Y_i\neq Y_{i+1}\)
题解
先考虑相邻两个已染色格子中间的未染色非空连续段，考虑只有一段的时候的胜负情况。手动模拟小数据可以发现，当两边颜色一样时，双方一共一定只会操作奇数次；而两边颜色不一样时，双方一共只会操作偶数次。考虑归纳地证明这个结论：设 \(f_i/g_i\) 表示长度为 \(i\) 的连续段，两边颜色一样/不一样，双方操作总次数的奇偶性。
\[f_1=1,g_0=g_1=0 \]\[f_{i}=g_j\oplus g_{i-1-j} \oplus 1=1(0\le j\le i-1) \]\[g_{i}=g_j\oplus f_{i-1-j} \oplus 1=0(0\le j\le i-2) \]有了这个结论，中间的那些未染色连续段的贡献相当于是交换先后手，所以现在只需要考虑 \(m\le 1\) 的情况。之后在交换了先后手的前提下讨论。
\(m=0\) 的时候，可以采取一个经典的策略就是取对称。所以当 \(m\) 是奇数的时候先手必胜，它可以先把中心占领，之后后手不管怎么取，就跟它取对称；当 \(m\) 是偶数的时候后手必胜，不管先手怎么取，后手跟它取位置对称颜色相反。
\(m=1\) 的时候比较复杂，设两边的未染色连续段的长度分别为 \(x,y\)。当 \(x,y\) 至少有一个大于 \(1\) 的时候，这两个段就可以拿来交换先后手，具体方法就是在第 \(1\) 个格子或者第 \(n\) 个格子染色，染与 \(Y_1\) 不同的颜色即可。讨论 \(t=[x>1]+[y>1]\) 的大小。
当 \(t=0\) 时，这种情况是平凡的，先后手情况固定。
当 \(t=1\) 时，Takahashi （不是先手）必胜，因为它可以第一步操作根据情况调整先后手，保证自己必胜。
当 \(t=2\) 时，Takahashi 显然不能直接取调整先后手，因为 Aoki 可以紧接着再调整回来。同理如果 Takahashi 没有调整，Aoki 也不会急着调整。似乎到这里不太好继续进行下去，但是，这种情况似乎也有一点优美的对称性，如果 Takahashi 的第一步操作能让 \(x=y\)，并调整先后手，那之后就可以像 \(m=0\) 的时候一样，不断跟 Aoki 取对称即可。这种情况可以发生当且仅当 \(|x-y|>1\)，所以不妨再按 \(|x-y|\) 的大小讨论
当 \(|x-y|=0\) ，即 \(x=y\) 时，直接取对称，那么对答案不影响。
当 \(|x-y|=1\) 时，如果 Takahashi 是先手，那么它直接让 \(|x-y|=0\) 转成他是后手，所以此时 Takahashi 必胜。否则，Takahashi 只能让新的 \(x',y'\) 满足 \(|x'-y'|=1\) ，否则一定会切换到 Aoki 的必胜态。这样操作后，Aoki 面临的局面就和 Takahashi 一样了，那么它也会这么做。双方最后一次这样操作的人就赢了，所以数一下会被操作的格子的奇偶性即可。
代码
#include <bits/stdc++.h>
#define re(i, x, y) for (int i = (x); i < (y); ++i)
#define rep(i, x, y) for (int i = (x); i <= (y); ++i)
#define repp(i, x, y, d) for (int i = (x); i <= (y); i += (d))
#define reep(i, x, y) for (int i = (x); i <= (y); i <<= 1)
#define pe(i, x, y) for (int i = (x) - 1; i >= (y); --i)
#define per(i, x, y) for (int i = (x); i >= (y); --i)
#define rep_e(i, u) for (int i = head[(u)]; i; i = e[i].nxt)
#define vi vector<int>
#define vL vector<LL>
#define vii vector<pii>
#define viL vector<piL>
#define vLi vector<pLi>
#define vLL vector<pLL>
#define eb emplace_back
#define pb pop_back
#define mp make_pair
#define pii pair<int, int>
#define piL pair<int, LL>
#define pLi pair<LL, int>
#define pLL pair<LL, LL>
#define lowbit(x) ((x) & (-(x)))
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define debug(x) cout << #x << " = " << x << endl
using namespace std;
typedef unsigned int ui;
typedef long long LL;
typedef unsigned long long ULL;
typedef double db;
#define getchar() (SB == TB && (TB = (SB = BB) + fread(BB, 1, 1 << 16, stdin), SB == TB) ? EOF : *SB++)
char BB[1 << 16], *SB = BB, *TB = BB;
template<typename T> void read(T &n) {
T w = 1;
n = 0;
char ch = getchar();
for ( ; !isdigit(ch); ch = getchar()) {
if (ch == '-') {
w = -1;
}
}
for ( ; isdigit(ch); ch = getchar()) {
n = n * 10 + (ch & 15);
}
n *= w;
}
template<typename T> void chkmn(T &a, const T &b) {
a = a > b ? b : a;
}
template<typename T> void chkmx(T &a, const T &b) {
a = a < b ? b : a;
}
int MOD;
int adt(const LL &a) {
return (a % MOD + MOD) % MOD;
}
int inc(const int &a, const int &b) {
return a + b >= MOD ? a + b - MOD : a + b;
}
int dec(const int &a, const int &b) {
return a - b < 0 ? a - b + MOD : a - b;
}
int mul(const int &a, const int &b) {
return 1LL * a * b % MOD;
}
int sqr(const int &a) {
return 1LL * a * a % MOD;
}
void Adt(LL &a) {
a = (a % MOD + MOD) % MOD;
}
void Inc(int &a, const int &b) {
a = a + b >= MOD ? a + b - MOD : a + b;
}
void Dec(int &a, const int &b) {
a = a - b < 0 ? a - b + MOD : a - b;
}
void Mul(int &a, const int &b) {
a = 1LL * a * b % MOD;
}
void Sqr(int &a) {
a = 1LL * a * a % MOD;
}
int fsp(int a, int x = MOD - 2) {
int res = 1;
for ( ; x; x >>= 1, Sqr(a)) {
if (x & 1) {
Mul(res, a);
}
}
return res;
}
const int maxn = 2e5 + 5;
LL n, m;
LL x[maxn], y[maxn];
int main() {
#ifdef sword
freopen("test.in", "r", stdin);
#endif
read(n), read(m);
if (!m) {
puts(n & 1 ? "Takahashi" : "Aoki");
return 0;
}
rep(i, 1, m) {
read(x[i]), read(y[i]);
}
bool fl = 0;
re(i, 1, m) {
if (y[i + 1] == y[i]) {
fl ^= 1;
}
}
if (x[1] == 2) {
fl ^= 1;
}
if (x[m] == n - 1) {
fl ^= 1;
}
int t = (x[1] > 2) + (x[m] < n - 1);
if (t == 1) {
puts("Takahashi");
}
else if (t == 2) {
if (x[1] == n - x[m] + 1) {
puts(fl ? "Takahashi" : "Aoki");
}
else {
if (abs(x[1] - (n - x[m] + 1)) > 1) {
puts("Takahashi");
}
else {
if (!fl) {
puts("Takahashi");
}
else {
puts(((x[1] - 1) / 2 + (n - x[m]) / 2) & 1 ? "Takahashi" : "Aoki");
}
}
}
}
else {
puts(fl ? "Takahashi" : "Aoki");
}
return 0;
}