分数: 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 如果他们在该查询中沿着道路的中途相遇。
示例输入 1
4 1 1 2 2 3 2 4 1 2
示例输出 1
Road
在第一个也是唯一一个查询中,高桥和青木同时离开城镇 1 和镇 2分别,他们将在中途相遇 1-st 路,所以我们应该打印 Road.
示例输入 2
5 2 1 2 2 3 3 4 4 5 1 3 1 5
示例输出 2
Town Town
在第一个查询中,高桥和青木同时离开城镇 1 和镇 3分别,他们将在镇见面 2,所以我们应该打印 Town.
在第一个查询中,高桥和青木同时离开城镇 1 和镇 5分别,他们将在镇见面 3,所以我们应该打印 Town.
示例输入 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
示例输出 3
Town Road Town Town Town Town Road Road Road