#ABC209D. [ABC209D] 碰撞(Collision)
[ABC209D] 碰撞(Collision)
题目描述
AtCoder
国由 个城镇和 条道路组成,城镇编号从 到 。第 条道路 连接城镇 和城镇 ,使得可以从任何城镇到达任何其他城镇。所有道路长度相同。
你将收到 个查询。在第 个查询 中,给定整数 和 ,解决以下问题:
小高现在在城镇 ,小李现在在城镇 。他们将同时离开城镇并以相同的速度开始旅行,小高前往城镇 ,小李前往城镇 。
确定他们是否会在某个城镇相遇或在某条道路的中途相遇。这里假设他们都沿最短路径行走,通过城镇的时间可以忽略不计。
输入格式
第一行输入点数 和询问次数 。
第二行到第 行,第 行输入两个数 ,表示第 条边连接的两个点。
从第 起的 行,第 行输入两个数 ,表示第 次询问的两个点。
输出格式
输出 行。第 行 应包含 "Town"
,如果小高和小李在第 个查询中将在城镇相遇,或者 "Road"
,如果他们在该查询中将在道路中途相遇。
输入输出样例 #1
输入 #1
4 1
1 2
2 3
2 4
1 2
输出 #1
Road
输入输出样例 #2
输入 #2
5 2
1 2
2 3
3 4
4 5
1 3
1 5
输出 #2
Town
Town
输入输出样例 #3
输入 #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
说明/提示
样例 1 解释
在第一个也是唯一的查询中,小高和小李分别同时离开城镇 和城镇 ,他们将在第 条道路的中途相遇,所以我们应该打印 "Road"
。
样例 2 解释
在第一个查询中,小高和小李分别同时离开城镇 和城镇 ,他们将在城镇 相遇,所以我们应该打印 "Town"
。
在第二个查询中,小高和小李分别同时离开城镇 和城镇 ,他们将在城镇 相遇,所以我们应该打印 "Town"
。
数据规模与约定
- 输入的数值均为整数;
- ,;
- ,且对于同一个 ,都有 ,。
- 可以从每个城镇到达每个城镇