#ABC209D. Collision
Collision
题目描述
有 个城镇,编号 到 , 条双向道路把它们连成一棵树。
现在有 次询问。第 次询问给出两个城镇 和 :高桥从 出发,青木从 出发,两人同时出发,每单位时间沿最短路走一条边。
如果两人在某个城镇相遇,输出 Town;如果两人在一条道路中间相遇,输出 Road。
输入格式
第一行两个整数 、。
接下来 行,每行两个整数 、,表示城镇 和 之间有一条道路。
接下来 行,每行两个整数 、,表示一次询问。
输出格式
输出 行,每行一个字符串,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
样例解释
第一组样例中,两人分别从 和 出发,距离为 。他们同时走这条边,会在道路中间相遇,所以输出 Road。
第二组样例中:
- 到 的距离是 ,两人在城镇 相遇,输出
Town; - 到 的距离是 ,在道路中间相遇,输出
Road; - 到 的距离是 ,在道路中间相遇,输出
Road。
数据范围与约定
| 子任务 | 分值 | 限制 |
|---|---|---|
| ,, |