Adjacent Game

AtCoder

IDttpc2024_2_n

Time2000ms

Memory256MB

Difficulty—

You are given a tree with $N$ vertices. The vertices of the tree are numbered $1, 2, \dots, N$, and the $i$\-th edge $(1 \leq i \leq N-1)$ connects vertex $u_i$ and vertex $v_i$. Alice and Bob play a game where they alternately mark vertices with their own markers. Initially, no vertices are marked. First, Alice chooses any vertex and marks it with her marker. Then, starting with Bob, the two players alternate performing the following operation. The player who cannot make a move loses, and the other player wins. * Choose a vertex $v$ that satisfies the following conditions: * Vertex $v$ is not marked. * There exists a vertex $u$ connected to $v$ by an edge such that $u$ is marked with the opponent's marker. * Mark the chosen vertex $v$ with their own marker. Determine the winner when both players adopt the optimal strategy for their own victory. ## Constraints * All input values are integers. * $1 \leq N \leq 2 \times 10^5$ * $1 \leq u_i, v_i \leq N$ * The given graph is a tree. ## Input The input is given in the following format: $N$ $u_1$ $v_1$ $\vdots$ $u_{N-1}$ $v_{N-1}$ [samples]

Samples

Input #1

Output #1

Alice

For example, consider the following scenario:

1.  Alice starts by marking vertex $1$ with her marker.
2.  Bob marks vertex $2$ (vertex $1$ is marked by the opponent and is connected to vertex $2$ by an edge).
3.  Alice marks vertex $3$ (vertex $2$ is marked by the opponent and is connected to vertex $3$ by an edge).
4.  Bob marks vertex $4$ (vertex $3$ is marked by the opponent and is connected to vertex $4$ by an edge).
5.  Alice marks vertex $5$ (vertex $2$ is marked by the opponent and is connected to vertex $5$ by an edge).
6.  Bob cannot make a move. Alice wins.

In this tree, Alice has a winning strategy, so you should output `Alice`.

Input #2

Output #2

Bob

Input #3

Output #3

Alice

API Response (JSON)

{
  "problem": {
    "name": "Adjacent Game",
    "description": {
      "content": "You are given a tree with $N$ vertices. The vertices of the tree are numbered $1, 2, \\dots, N$, and the $i$\\-th edge $(1 \\leq i \\leq N-1)$ connects vertex $u_i$ and vertex $v_i$. Alice and Bob play a ",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "ttpc2024_2_n"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given a tree with $N$ vertices. The vertices of the tree are numbered $1, 2, \\dots, N$, and the $i$\\-th edge $(1 \\leq i \\leq N-1)$ connects vertex $u_i$ and vertex $v_i$.\nAlice and Bob play a ...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments