Problem:


  MathJax.Hub.Config({ tex2jax: { inlineMath: [["$","$"], ["\\(","\\)"]], processEscapes: true }});

Problem H:
DisconnectedGame

  Taro と Hanako がゲームをしている.

  最初に, 非連結な無向グラフ(二重辺や self loop を含まない) が与えられる. Taro と Hanako は交互に操作を行う. 操作では, 辺で直接つながれていない異なる2 頂点を選び, その間に辺を加える. グラフを連結にしたほうが負けである.

  グラフには $V$ 個の頂点がある. $V \times V$ の行列が与えられる. 行列の $(i, j)$-成分が'Y' であるとき $i$ と $j$ の間には辺があり, 'N' であるときは辺が無い.

  両者が最善に操作をしたとき, どちらが勝つかを出力せよ.

Constraints

$V$ will be between 2 and 1,000, inclusive.

$a_{i,i}$ will be 'N'.

$a_{i,j}$ will be 'Y' or 'N'.

$a_{i,j}$ will be equal to $a_{j,i}$.

The graph will not be connected.

Input

  入力は以下の形式で与えられる:

  

  
$V$

$a_{1,1}$ ... $a_{1,V}$

...

$a_{V,1}$ ... $a_{V,V}$

Output

Taro が勝つ場合には "Taro" (quotes for clarity), Hanako が勝つ場合には "Hanako" (quotes for clarity) と 1 行に出力せよ.

Sample Input 1

3
NNN
NNN
NNN

Sample Output 1

Taro

Sample Input 2

5
NNYNN
NNNNN
YNNNN
NNNNY
NNNYN

Sample Output 2

Hanako

Sample Input 3

8
NYNNNNNN
YNNYNNYN
NNNNNNNY
NYNNNNYN
NNNNNNNN
NNNNNNNN
NYNYNNNN
NNYNNNNN

Sample Output 3

Taro


Sample input:
3
NNN
NNN
NNN


Sample output:
Taro

Submission status: Accepted

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline
write = sys.stdout.write
def solve():
    N = int(readline())
    G = [[] for i in range(N)]
    for i in range(N):
        *vs, = readline()
        for j in range(N):
            if vs[j] == "Y":
                G[i].append(j)
    d = 0
    C = [0, 0]
    used = [0]*N
    for i in range(N):
        d += len(G[i])
        if used[i]:
            continue
        used[i] = 1
        que = deque([i])
        c = 0
        while que:
            v = que.popleft()
            c += 1
            for w in G[v]:
                if used[w]:
                    continue
                used[w] = 1
                que.append(w)
        C[c % 2] += 1
    r0 = (N*(N-1)//2 - d//2) & 1
    memo = {}
    def dfs(i, p, q):
        key = (p, q)
        if key in memo:
            return memo[key]
        if p+q == 2:
            r = (q == 2) ^ r0
            memo[key] = e = r ^ (i & 1)
            return e
        r = 0
        if p > 1 or (p and q):
            if dfs(i+1, p-1, q) == 0:
                r = 1
        if q > 1:
            if dfs(i+1, p+1, q-2) == 0:
                r = 1
        memo[key] = r
        return r
    if dfs(0, C[0], C[1]):
        write("Taro\n")
    else:
        write("Hanako\n")
solve()