{"trustable":true,"prependHtml":"\u003cstyle type\u003d\"text/css\"\u003e\n .markdown img {\n max-width: 900px;\n display: block;\n margin: 10px auto;\n }\n .markdown code {\n display: inline-block;\n padding: 0 4px;\n margin: 0;\n background-color: rgba(0, 0, 0, 0.04);\n border-radius: 3px;\n font-weight: bold;\n }\n .markdown pre code {\n display: block;\n padding: 20px;\n font-weight: normal;\n }\n .markdown table {\n width: 100%;\n table-layout: fixed;\n border-collapse: collapse;\n }\n .markdown table th {\n font-size: 13px;\n text-align: left;\n padding: 10px;\n border: 1px solid #e0e0e0;\n background: #f1f1f1;\n }\n .markdown table td {\n font-size: 14px;\n padding: 5px 10px;\n border: 1px solid #e0e0e0;\n }\n .markdown-form-widget .markdown-notice p {\n padding: 0;\n margin: 0;\n color: #999999;\n font-size: 11px;\n }\n\u003c/style\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"latex latex-raw\"\u003eAlice and Bob are playing a game on an undirected Tree. Alice plays first. In first move, Alice can mark any vertex of the tree. After first move, they will play alternatively and each player will choose a vertex which is adjacent to the LAST marked vertex and mark it. Note that a player cannot mark a vertex which was already marked in a previous move. If a player can not choose any vertex, he or she loses.\u003cp\u003e\u003c/p\u003e\n\n\u003cp\u003eGiven that both players play optimally, can you find out who will win, even before the game begins.\u003c/p\u003e\n\n\u003cp\u003e\u003c/p\u003e\u003ch2\u003eInput\u003c/h2\u003e\u003cp\u003e\u003c/p\u003e\n\n\u003cp\u003eFirst line contains \u003cstrong\u003eT\u003c/strong\u003e, the number of test cases. Then description of each test case follows. First line contains a number \u003cstrong\u003eN\u003c/strong\u003e, the number of vertices in a tree. The next \u003cstrong\u003eN\u003c/strong\u003e-\u003cstrong\u003e1\u003c/strong\u003e lines contains two space separated integers \u003cstrong\u003ea\u003c/strong\u003e \u003cstrong\u003eb\u003c/strong\u003e represents an undirected edge from \u003cstrong\u003ea\u003c/strong\u003e to \u003cstrong\u003eb\u003c/strong\u003e. (\u003cstrong\u003e1\u003c/strong\u003e ≤ \u003cstrong\u003ea\u003c/strong\u003e, \u003cstrong\u003eb\u003c/strong\u003e ≤ \u003cstrong\u003eN\u003c/strong\u003e).\u003c/p\u003e\n\n\u003cp\u003eIt is known that \u003cstrong\u003eT\u003c/strong\u003e ≤ \u003cstrong\u003e25\u003c/strong\u003e, \u003cstrong\u003eN\u003c/strong\u003e ≤ \u003cstrong\u003e50000\u003c/strong\u003e.\u003c/p\u003e\n\n\u003cp\u003e\u003c/p\u003e\u003ch2\u003eOutput\u003c/h2\u003e\u003cp\u003e\u003c/p\u003e\n\n\u003cp\u003eOutput \u003cstrong\u003eT\u003c/strong\u003e lines, each containing the answer for one test case. Output \"\u003cstrong\u003eAlice\u003c/strong\u003e\" if Alice wins the game, or \"\u003cstrong\u003eBob\u003c/strong\u003e\" otherwise. \\[quotes for clarity only\\].\u003c/p\u003e\n\n\u003c/div\u003e"}},{"title":"Example","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e2\n2\n1 2\n3\n1 2\n1 3\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eBob\nAlice\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}