{"problem":{"name":"Black and White Tree","description":{"content":"There is a tree with $N$ vertices numbered $1$ through $N$. The $i$\\-th of the $N-1$ edges connects vertices $a_i$ and $b_i$. Initially, each vertex is uncolored. Takahashi and Aoki is playing a game ","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"agc014_d"},"statements":[{"statement_type":"Markdown","content":"There is a tree with $N$ vertices numbered $1$ through $N$. The $i$\\-th of the $N-1$ edges connects vertices $a_i$ and $b_i$.\nInitially, each vertex is uncolored.\nTakahashi and Aoki is playing a game by painting the vertices. In this game, they alternately perform the following operation, starting from Takahashi:\n\n*   Select a vertex that is not painted yet.\n*   If it is Takahashi who is performing this operation, paint the vertex white; paint it black if it is Aoki.\n\nThen, after all the vertices are colored, the following procedure takes place:\n\n*   Repaint every white vertex that is adjacent to a black vertex, in black.\n\nNote that all such white vertices are repainted simultaneously, not one at a time.\nIf there are still one or more white vertices remaining, Takahashi wins; if all the vertices are now black, Aoki wins. Determine the winner of the game, assuming that both persons play optimally.\n\n## Constraints\n\n*   $2 ≤ N ≤ 10^5$\n*   $1 ≤ a_i,b_i ≤ N$\n*   $a_i ≠ b_i$\n*   The input graph is a tree.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$\n$a_1$ $b_1$\n:\n$a_{N-1}$ $b_{N-1}$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"agc014_d","tags":[],"sample_group":[["3\n1 2\n2 3","First\n\nBelow is a possible progress of the game:\n\n*   First, Takahashi paint vertex $2$ white.\n*   Then, Aoki paint vertex $1$ black.\n*   Lastly, Takahashi paint vertex $3$ white.\n\nIn this case, the colors of vertices $1$, $2$ and $3$ after the final procedure are black, black and white, resulting in Takahashi's victory."],["4\n1 2\n2 3\n2 4","First"],["6\n1 2\n2 3\n3 4\n2 5\n5 6","Second"]],"created_at":"2026-03-03 11:01:14"}}