{"raw_statement":[{"iden":"problem statement","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 game where they alternately mark vertices with their own markers. Initially, no vertices are marked.\nFirst, 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.\n\n*   Choose a vertex $v$ that satisfies the following conditions:\n    *   Vertex $v$ is not marked.\n    *   There exists a vertex $u$ connected to $v$ by an edge such that $u$ is marked with the opponent's marker.\n*   Mark the chosen vertex $v$ with their own marker.\n\nDetermine the winner when both players adopt the optimal strategy for their own victory."},{"iden":"constraints","content":"*   All input values are integers.\n*   $1 \\leq N \\leq 2 \\times 10^5$\n*   $1 \\leq u_i, v_i \\leq N$\n*   The given graph is a tree."},{"iden":"input","content":"The input is given in the following format:\n\n$N$\n$u_1$ $v_1$\n$\\vdots$\n$u_{N-1}$ $v_{N-1}$"},{"iden":"sample input 1","content":"5\n1 2\n2 3\n3 4\n2 5"},{"iden":"sample output 1","content":"Alice\n\nFor example, consider the following scenario:\n\n1.  Alice starts by marking vertex $1$ with her marker.\n2.  Bob marks vertex $2$ (vertex $1$ is marked by the opponent and is connected to vertex $2$ by an edge).\n3.  Alice marks vertex $3$ (vertex $2$ is marked by the opponent and is connected to vertex $3$ by an edge).\n4.  Bob marks vertex $4$ (vertex $3$ is marked by the opponent and is connected to vertex $4$ by an edge).\n5.  Alice marks vertex $5$ (vertex $2$ is marked by the opponent and is connected to vertex $5$ by an edge).\n6.  Bob cannot make a move. Alice wins.\n\nIn this tree, Alice has a winning strategy, so you should output `Alice`."},{"iden":"sample input 2","content":"4\n1 2\n3 4\n3 2"},{"iden":"sample output 2","content":"Bob"},{"iden":"sample input 3","content":"7\n1 2\n2 3\n3 4\n3 5\n1 6\n6 7"},{"iden":"sample output 3","content":"Alice"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}