33OJ
登录 注册

#ABC209D. Collision

Collision

题目描述

有 NN 个城镇,编号 11 到 NN,N−1N-1 条双向道路把它们连成一棵树。

现在有 QQ 次询问。第 ii 次询问给出两个城镇 cic_i 和 did_i:高桥从 cic_i 出发,青木从 did_i 出发,两人同时出发,每单位时间沿最短路走一条边。

如果两人在某个城镇相遇,输出 Town;如果两人在一条道路中间相遇,输出 Road。

输入格式

第一行两个整数 NN、QQ。

接下来 N−1N-1 行,每行两个整数 aia_i、bib_i,表示城镇 aia_i 和 bib_i 之间有一条道路。

接下来 QQ 行,每行两个整数 cic_i、did_i,表示一次询问。

输出格式

输出 QQ 行,每行一个字符串,Town 或 Road。

样例

4 1
1 2
2 3
2 4
1 2
Road
5 3
1 2
2 3
2 4
4 5
1 3
1 5
3 5
Town
Road
Road

样例解释

第一组样例中,两人分别从 11 和 22 出发,距离为 11。他们同时走这条边,会在道路中间相遇,所以输出 Road。

第二组样例中:

  • 11 到 33 的距离是 22,两人在城镇 22 相遇,输出 Town;
  • 11 到 55 的距离是 33,在道路中间相遇,输出 Road;
  • 33 到 55 的距离是 33,在道路中间相遇,输出 Road。

数据范围与约定

子任务 分值 限制
11 100100 2≤N≤2×1052 \le N \le 2 \times 10^5,1≤Q≤2×1051 \le Q \le 2 \times 10^5,1≤ai,bi,ci,di≤N1 \le a_i,b_i,c_i,d_i \le N