← 返回题目列表

AtCoder · abc354_e

H. 删除对

中文机器翻译题面 查看原题

分数: 475 点

问题陈述

高桥和青木正在玩游戏 N 卡。正面 i第一张卡有 上面写着 A_i ,背面有 上面写着 B_i 。最初, N 卡片放在桌子上。高桥先行,两名玩家轮流执行以下操作:

  • 从牌桌上选择一对正面数字相同或背面数字相同的牌,并将这两张牌从牌桌上移走。如果不存在这样的牌对,则玩家不能执行该操作。

最先无法执行操作的玩家失败,另一位玩家获胜。 如果两名玩家都发挥最佳,确定谁获胜。

约束

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

输入

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

N
A_1 B_1
A_2 B_2
\vdots
A_N B_N

输出

打印 Takahashi 如果高桥在两名玩家都发挥最佳状态时获胜,并且 Aoki 否则。


示例输入 1

5
1 9
2 5
4 9
1 4
2 5

示例输出 1

Aoki

如果高桥首先删除

  • 第一张和第三张牌:青木可以通过移除第二张和第五张牌来获胜。

  • 第一张和第四张牌:青木可以通过移除第二张和第五张牌来获胜。

  • 第二张和第五张牌:青木可以通过移除第一张和第三张牌来获胜。

这是高桥在第一步中可以移除的仅有的三对牌,青木在所有情况下都可以获胜。因此,答案是青木。


示例输入 2

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

示例输出 2

Takahashi