Remove Pairs

AtCoder

IDabc354_e

Time2000ms

Memory256MB

Difficulty—

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$ [samples]

Samples

Input #1

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.

Input #2

Output #2

Takahashi

API Response (JSON)

{
  "problem": {
    "name": "Remove Pairs",
    "description": {
      "content": "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 t",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "abc354_e"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "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 t...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments