Remove Pairs

题目描述

Takahashi 和 Aoki 正在用 $N$ 张卡片玩一个游戏。第 $i$ 张卡片的正面写着 $A_i$，背面写着 $B_i$。最初，将这 $N$ 张卡片摊放在桌子上。Takahashi 先手，双方轮流执行以下操作：

从桌上选择一对卡片，使得它们的正面数字相同或背面数字相同，并将这两张卡片从桌上移除。如果不存在这样的卡片对，则该玩家无法执行操作。

第一个无法执行操作的玩家输，另一名玩家获胜。 当两名玩家都以最优方式行棋时，判定谁会获胜。

输入格式

输入按下述格式从标准输入给出： $N$ $A_1$ $B_1$ $A_2$ $B_2$ $\vdots$ $A_N$ $B_N$

输出格式

如果在双方都以最优方式行棋时 Takahashi 会获胜，则输出 $Takahashi$，否则输出 $Aoki$。

5
1 9
2 5
4 9
1 4
2 5

Aoki

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

Takahashi

提示

$1 \leq N \leq 18$ $1 \leq A_i, B_i \leq 10^9$ 所有输入值均为整数。如果 Takahashi 先移除

第一张和第三张卡片：Aoki 可以通过移除第二张和第五张卡片获胜。

第一张和第四张卡片：Aoki 可以通过移除第二张和第五张卡片获胜。

第二张和第五张卡片：Aoki 可以通过移除第一张和第三张卡片获胜。

这些是 Takahashi 首步可移除的唯三对卡片，且在所有情况下 Aoki 都能获胜。因此，答案是 Aoki。

标签: AtCoder|abc354E

来源

AtCoder|abc354E