102093: [AtCoder]ABC209 D - Collision

Problem Statement

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.

You 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:

• 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.

Constraints

• $2 \leq N \leq 10^5$
• $1 \leq Q \leq 10^5$
• $1 \leq a_i < b_i \leq N\, (1 \leq i \leq N-1)$
• $1 \leq c_i < d_i \leq N\, (1 \leq i \leq Q)$
• All values in input are integers.
• It is possible to get from every town to every town by using some roads.

Input

Input is given from Standard Input in the following format:

$N$ $Q$
$a_1$ $b_1$
$a_2$ $b_2$
$\hspace{0.6cm}\vdots$
$a_{N-1}$ $b_{N-1}$
$c_1$ $d_1$
$c_2$ $d_2$
$\hspace{0.6cm}\vdots$
$c_Q$ $d_Q$

Output

Print $Q$ lines. The $i$-th line $(1 \leq i \leq Q)$ should contain Town if Takahashi and Aoki will meet at a town in the $i$-th query, and Road if they meet halfway along a road in that query.

Sample Input 1

4 1
1 2
2 3
2 4
1 2

Sample Output 1

Road

In 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.

Sample Input 2

5 2
1 2
2 3
3 4
4 5
1 3
1 5

Sample Output 2

Town
Town

In 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.

In 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.

Sample Input 3

9 9
2 3
5 6
4 8
8 9
4 5
3 4
1 9
3 7
7 9
2 5
2 6
4 6
2 4
5 8
7 8
3 6
5 6

Sample Output 3

Town
Road
Town
Town
Town
Town
Road
Road
Road

问题描述

高桥王国由$N$个城镇和$N-1$条道路组成，城镇编号从1到$N$。第$i$条道路（$1 \leq i \leq N-1$）连接城镇$a_i$和城镇$b_i$，所以可以通过一些道路从每个城镇到达每个城镇。**所有道路长度相同。**

你将收到$Q$个查询。在第$i$个查询（$1 \leq i \leq Q$）中，给定整数$c_i$和$d_i$，解决以下问题：

• 高桥现在在城镇$c_i$，青木现在在城镇$d_i$。他们会同时离开城镇，以相同的速度出发，高桥前往城镇$d_i$，青木前往城镇$c_i$。判断他们是否会相遇在城镇还是在道路的中点。假设他们都沿着最短路径行驶，通过城镇的时间可以忽略不计。

约束

• $2 \leq N \leq 10^5$
• $1 \leq Q \leq 10^5$
• $1 \leq a_i < b_i \leq N\, (1 \leq i \leq N-1)$
• $1 \leq c_i < d_i \leq N\, (1 \leq i \leq Q)$
• 输入中的所有值都是整数。
• 可以通过一些道路从每个城镇到达每个城镇。

输入

输入从标准输入以以下格式给出：

$N$ $Q$
$a_1$ $b_1$
$a_2$ $b_2$
$\hspace{0.6cm}\vdots$
$a_{N-1}$ $b_{N-1}$
$c_1$ $d_1$
$c_2$ $d_2$
$\hspace{0.6cm}\vdots$
$c_Q$ $d_Q$

输出

打印$Q$行。 第$i$行（$1 \leq i \leq Q$）应包含Town，如果在第$i$个查询中高桥和青木会在城镇相遇，如果他们在道路上的中点相遇，则应包含Road。

样例输入1

4 1
1 2
2 3
2 4
1 2

样例输出1

Road

在唯一的一个查询中，高桥和青木分别从城镇1和2同时出发，他们将在第1条道路上的中点相遇，所以我们应该打印Road。

5 2
1 2
2 3
3 4
4 5
1 3
1 5

Town
Town

9 9
2 3
5 6
4 8
8 9
4 5
3 4
1 9
3 7
7 9
2 5
2 6
4 6
2 4
5 8
7 8
3 6
5 6

Town
Road
Town
Town
Town
Town
Road
Road
Road