← 返回题目列表

AtCoder · abc209_d

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 如果他们在该查询中沿着道路的中途相遇。


示例输入 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