E - Remove Pairs Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 475 点

問題文

高橋君と青木君は N 枚のカードを使ってとあるゲームをします。i 枚目のカードの表面には A_i が、裏面には B_i が書かれています。初めに場には N 枚のカードが並べられており、高橋君を先手として、2 人は以下の操作を交互に繰り返します。

  • 場にあるカードの中から表面同士に同じ数が書かれている、または裏面同士に同じ数が書かれている 2 枚のカードの組を選び、そのカードを場から取り除く。このようなカードの組が存在しない場合、操作を行えない。

先に操作を行えなくなった方が負けとなり、もう一方が勝ちとなります。 両者がそれぞれ勝つために最適な操作を選ぶ時、どちらが勝つか求めてください。

制約

  • 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

出力

2 人とも最適に操作を行なったとき、高橋君が勝つ場合は Takahashi と、青木君が勝つ場合は Aoki と出力せよ。

入力例 1

5
1 9
2 5
4 9
1 4
2 5

出力例 1

Aoki

髙橋君が最初に取り除いた 2 枚が

  • 1 枚目と 3 枚目のカードだった場合: 青木君は 2 枚目と 5 枚目のカードを取り除くことで勝つことができる。

  • 1 枚目と 4 枚目のカードだった場合: 青木君は 2 枚目と 5 枚目のカードを取り除くことで勝つことができる。

  • 2 枚目と 5 枚目のカードだった場合: 青木君は 1 枚目と 3 枚目のカードを取り除くことで勝つことができる。

髙橋君が最初の操作で取り除くことができるカードの組み合わせは以上の 3 通りのみで、髙橋君がどのような操作を行っても青木君が勝つことができるため、青木君が答えとなります。

入力例 2

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

出力例 2

Takahashi

Score : 475 points

Problem Statement

Takahashi and Aoki are playing a game using N cards. The front side of the i-th card has A_i written on it, and the back side has B_i written on it. Initially, the N cards are laid out on the table. With Takahashi going first, the two players take turns performing the following operation:

  • Choose a pair of cards from the table such that either the numbers on their front sides are the same or the numbers on their back sides are the same, and remove these two cards from the table. If no such pair of cards exists, the player cannot perform the operation.

The player who is first to be unable to perform the operation loses, and the other player wins. Determine who wins if both players play optimally.

Constraints

  • 1 \leq N \leq 18
  • 1 \leq A_i, B_i \leq 10^9
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N
A_1 B_1
A_2 B_2
\vdots
A_N B_N

Output

Print Takahashi if Takahashi wins when both players play optimally, and Aoki otherwise.

Sample Input 1

5
1 9
2 5
4 9
1 4
2 5

Sample Output 1

Aoki

If Takahashi first removes

  • the first and third cards: Aoki can win by removing the second and fifth cards.

  • the first and fourth cards: Aoki can win by removing the second and fifth cards.

  • the second and fifth cards: Aoki can win by removing the first and third cards.

These are the only three pairs of cards Takahashi can remove in his first move, and Aoki can win in all cases. Therefore, the answer is Aoki.

Sample Input 2

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

Sample Output 2

Takahashi