AT_abc354_e [ABC354E] Remove Pairs

题目描述

高桥君和青木君用 $N$ 张卡牌进行一场游戏。第 $i$ 张卡牌的正面写有 $A_i$，背面写有 $B_i$。一开始，场上摆放着 $N$ 张卡牌，高桥君先手，二人轮流进行如下操作：

• 从场上的卡牌中选择一对卡牌，这对卡牌要么正面数字相同，要么背面数字相同，然后将这两张卡牌从场上移除。如果不存在这样的卡牌对，则无法进行操作。

无法进行操作的一方判负，另一方获胜。当两人都采取最优策略时，请判断谁会获胜。

输入格式

输入以如下格式从标准输入给出。

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

输出格式

当高桥君获胜时输出 Takahashi，青木君获胜时输出 Aoki。

输入输出样例 #1

输入 #1

5
1 9
2 5
4 9
1 4
2 5

输出 #1

Aoki

输入输出样例 #2

输入 #2

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

输出 #2

Takahashi

说明/提示

限制条件

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

样例解释 1

若高桥君第一次移除的是第 1 张和第 3 张卡牌：青木君可以移除第 2 张和第 5 张卡牌并获胜。
若高桥君第一次移除的是第 1 张和第 4 张卡牌：青木君可以移除第 2 张和第 5 张卡牌并获胜。
若高桥君第一次移除的是第 2 张和第 5 张卡牌：青木君可以移除第 1 张和第 3 张卡牌并获胜。
高桥君第一次能移除的卡牌组合只有上述 3 种，无论他如何选择，青木君都能获胜，因此答案为青木君。

由 ChatGPT 4.1 翻译