D - 碰撞

得分: $400$ 分

问题描述

高桥王国由 $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。

4 1
1 2
2 3
2 4
1 2

Road

在第一个且唯一一个询问中，高桥和青木同时离开城镇 $1$ 和城镇 $2$，他们将在第 $1$ 条道路的中间碰面，所以我们应该输出 Road。

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

Town
Town

在第一个询问中，高桥和青木同时离开城镇 $1$ 和城镇 $3$，他们将在城镇 $2$ 碰面，所以我们应该输出 Town。

在第二个询问中，高桥和青木同时离开城镇 $1$ 和城镇 $5$，他们将在城镇 $3$ 碰面，所以我们应该输出 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