{"problem":{"name":"Collision","description":{"content":"The Kingdom of Takahashi is made up of $N$ towns and $N-1$ roads, where the towns are numbered $1$ through $N$. The $i$\\-th road $(1 \\leq i \\leq N-1)$ connects Town $a_i$ and Town $b_i$, so that you c","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc209_d"},"statements":[{"statement_type":"Markdown","content":"The Kingdom of Takahashi is made up of $N$ towns and $N-1$ roads, where the towns are numbered $1$ through $N$. The $i$\\-th road $(1 \\leq i \\leq N-1)$ connects Town $a_i$ and Town $b_i$, so that you can get from every town to every town by using some roads. **All the roads have the same length.**\nYou will be given $Q$ queries. In the $i$\\-th query $(1 \\leq i \\leq Q)$, given integers $c_i$ and $d_i$, solve the following problem:\n\n*   Takahashi is now at Town $c_i$ and Aoki is now at Town $d_i$. They will leave the towns simultaneously and start traveling at the same speed, Takahashi heading to Town $d_i$ and Aoki heading to Town $c_i$. Determine whether they will meet at a town or halfway along a road. Here, assume that both of them travel along the shortest paths, and the time it takes to pass towns is negligible.\n\n## Constraints\n\n*   $2 \\leq N \\leq 10^5$\n*   $1 \\leq Q \\leq 10^5$\n*   $1 \\leq a_i < b_i \\leq N\\, (1 \\leq i \\leq N-1)$\n*   $1 \\leq c_i < d_i \\leq N\\, (1 \\leq i \\leq Q)$\n*   All values in input are integers.\n*   It is possible to get from every town to every town by using some roads.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$ $Q$\n$a_1$ $b_1$\n$a_2$ $b_2$\n$\\hspace{0.6cm}\\vdots$\n$a_{N-1}$ $b_{N-1}$\n$c_1$ $d_1$\n$c_2$ $d_2$\n$\\hspace{0.6cm}\\vdots$\n$c_Q$ $d_Q$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc209_d","tags":[],"sample_group":[["4 1\n1 2\n2 3\n2 4\n1 2","Road\n\nIn the first and only query, Takahashi and Aoki simultaneously leave Town $1$ and Town $2$, respectively, and they will meet halfway along the $1$\\-st road, so we should print `Road`."],["5 2\n1 2\n2 3\n3 4\n4 5\n1 3\n1 5","Town\nTown\n\nIn the first query, Takahashi and Aoki simultaneously leave Town $1$ and Town $3$, respectively, and they will meet at Town $2$, so we should print `Town`.\nIn the first query, Takahashi and Aoki simultaneously leave Town $1$ and Town $5$, respectively, and they will meet at Town $3$, so we should print `Town`."],["9 9\n2 3\n5 6\n4 8\n8 9\n4 5\n3 4\n1 9\n3 7\n7 9\n2 5\n2 6\n4 6\n2 4\n5 8\n7 8\n3 6\n5 6","Town\nRoad\nTown\nTown\nTown\nTown\nRoad\nRoad\nRoad"]],"created_at":"2026-03-03 11:01:14"}}