ユニークビジョンプログラミングコンテスト2025 春（AtCoder Beginner Contest 398）F,G問題メモ

def manacher(s):
    n = len(s)
    radius = [0] * n
    i, j = 0, 0
    while i < n:
        while i - j >= 0 and i + j < n and s[i - j] == s[i + j]:
            j += 1
        radius[i] = j
        k = 1
        while i - k >= 0 and i + k < n and k + radius[i - k] < j:
            radius[i + k] = radius[i - k]
            k += 1
        i += k
        j -= k
    return radius


def solve(s):
    n = len(s)
    t = '$' + '$'.join(s) + '$'
    radius = manacher(t)
    for i in range(n, n * 2 + 1):
        r = radius[i]
        if i + r != n * 2 + 1:
            continue
        j = i * 2 - n * 2
        return s + s[:j // 2][::-1]


s = input()
ans = solve(s)
print(ans)

import random


def rolling_hash(n, s, b, m):
    hf = 0
    hb = 0
    best_i = n
    bk = 1
    for i in range(n - 1, -1, -1):
        c = ord(s[i]) - 65
        hf = (hf + c * bk) % m
        bk = bk * b % m
        hb = (hb * b + c) % m
        if hf == hb:
            best_i = i
    return best_i


def solve(s):
    n = len(s)
    best_i = 0
    for _ in range(5):
        b = random.randrange(1, 998244353)
        best_i = max(best_i, rolling_hash(n, s, b, 998244353))
    ans = s + s[:best_i][::-1]
    return ans


s = input()
ans = solve(s)
print(ans)

def naive(state, memo={}):
    if state in memo:
        return memo[state]

    ee, eo, si, oo, edge = state
    if sum((ee, eo, si, oo)) <= 1 and edge == 0:
        return 0

    if edge == 1:
        if naive((ee, eo, si, oo, 0)) == 0:
            memo[state] = 1
            return 1

    if ee >= 2:
        if naive((ee - 1, eo, si, oo, edge ^ 1)) == 0:
            memo[state] = 1
            return 1

    if ee >= 1 and eo >= 1:
        if naive((ee - 1, eo, si, oo, edge ^ 1)) == 0:
            memo[state] = 1
            return 1

    if ee >= 1 and si >= 1:
        if naive((ee - 1, eo + 1, si - 1, oo, edge ^ 1)) == 0:
            memo[state] = 1
            return 1

    if ee >= 1 and oo >= 1:
        if naive((ee - 1, eo, si, oo, edge ^ 1)) == 0:
            memo[state] = 1
            return 1

    if eo >= 2:
        if naive((ee + 1, eo - 2, si, oo, edge ^ 1)) == 0:
            memo[state] = 1
            return 1
        if naive((ee, eo - 2, si, oo + 1, edge)) == 0:
            memo[state] = 1
            return 1

    if eo >= 1 and si >= 1:
        if naive((ee + 1, eo - 1, si - 1, oo, edge ^ 1)) == 0:
            memo[state] = 1
            return 1
        if naive((ee, eo - 1, si - 1, oo + 1, edge)) == 0:
            memo[state] = 1
            return 1

    if eo >= 1 and oo >= 1:
        if naive((ee, eo, si, oo - 1, edge)) == 0:
            memo[state] = 1
            return 1

    if si >= 2:
        if naive((ee, eo, si - 2, oo + 1, edge)) == 0:
            memo[state] = 1
            return 1

    if si >= 1 and oo >= 1:
        if naive((ee, eo + 1, si - 1, oo - 1, edge)) == 0:
            memo[state] = 1
            return 1

    if oo >= 2:
        if naive((ee + 2, eo, si, oo - 2, edge ^ 1)) == 0:
            memo[state] = 1
            return 1

    memo[state] = 0
    return 0


def solve(n, m, edges):
    # N 奇数の場合、二部グラフの頂点数は(偶,奇)となり、最終的な辺の数は必ず偶数 → 初期にある辺が奇数本なら先手勝ち
    if n % 2 == 1:
        return int(m % 2 == 1)

    links = [set() for _ in range(n)]
    for u, v in edges:
        u -= 1
        v -= 1
        links[u].add(v)
        links[v].add(u)
    ee = 0
    eo = 0
    si = 0
    oo = 0
    groups = [-1] * n
    for s in range(n):
        if groups[s] != -1:
            continue
        cur_groups = [1, 0]
        groups[s] = 0
        q = [s]
        while q:
            u = q.pop()
            gu = groups[u]
            for v in links[u]:
                if groups[v] != -1:
                    assert groups[v] == gu ^ 1
                    continue
                groups[v] = gu ^ 1
                q.append(v)
                cur_groups[groups[v]] += 1
        if cur_groups[0] % 2 == cur_groups[1] % 2 == 0:
            ee += 1
        elif cur_groups[0] % 2 == cur_groups[1] % 2 == 1:
            oo += 1
        elif sum(cur_groups) == 1:
            si += 1
        else:
            eo += 1

    edge = (oo % 2) ^ (m % 2)

    return naive((ee % 1, min(eo, 3), si % 4, oo % 2, edge))


n, m = map(int, input().split())
edges = [tuple(map(int, input().split())) for _ in range(m)]
ans = solve(n, m, edges)
if ans:
    print('Aoki')
else:
    print('Takahashi')