移除卡牌对

题目描述

高桥君和青木君用 $N$ 张卡进行游戏。第 $i$ 张卡的正面写着 $A_i$,背面写着 $B_i$。初始时,这 $N$ 张卡都放在桌上。高桥君先手,两人轮流执行以下操作:

从桌上选出一对卡,使得这两张卡正面的数字相同,或背面的数字相同,然后将这两张卡从桌上移除。如果桌上不存在这样的卡对,则该玩家无法进行操作。

最先无法进行操作的玩家失败,另一名玩家获胜。 判断两人都采取最优策略时谁会获胜。

输入格式

输入按以下格式从标准输入给出:

$N$
$A_1$ $B_1$
$A_2$ $B_2$
$\vdots$
$A_N$ $B_N$

输出格式

两人都采取最优策略时,若高桥君获胜则输出 Takahashi,否则输出 Aoki。

样例

5
1 9
2 5
4 9
1 4
2 5

Aoki

高桥君第一步可以移除的卡对只有以下三种:

• 移除第 1 张和第 3 张:青木君可以通过移除第 2 张和第 5 张获胜。
• 移除第 1 张和第 4 张:青木君可以通过移除第 2 张和第 5 张获胜。
• 移除第 2 张和第 5 张:青木君可以通过移除第 1 张和第 3 张获胜。

无论哪种情况青木君都能获胜,因此答案是 Aoki。

9
3 2
1 7
4 1
1 8
5 2
9 8
2 1
6 8
5 2

Takahashi

数据范围

• $1 \le N \le 18$
• $1 \le A_i, B_i \le 10^9$
• 所有输入值均为整数