Logo Daimayuan Online Judge

Home

时间限制:1 s 空间限制:256 MB

#869. Collision

附加文件 统计

题目描述

siyisss 的王国是由 $n$ 个村镇和 $n - 1$ 条双向道路构成的,村镇从 $1$ 到 $n$ 依次编号,每条双向道路连接两个不同的村镇,使得从任意一个村镇出发都可以到达任意一个村镇。接下来请你回答 $q$ 个问题,每次给出两个整数 $c$, $d$,表示现在分别有一个人在村镇 $c$,一个人在村镇 $d$,现在在 $c$ 的人要用最短的时间到达村镇$d$,在村镇 $d$ 的人要以最短的时间到达村镇 $c$,假设两人同时出发,两人的速度也是一样的,每条双向道路的长度也是一样的,请问两人相遇的时候是在某一个村镇,还是在某条双向道路上?

输入描述

第一行输入两个整数 $n$, $q$ 代表村镇的数量和询问的数量

接下来 $n - 1$ 行,每行两个整数用来描述一条双向道路

最后 $q$,每行两个整数代表 $c$, $d$

输出描述

对于每个询问,如果他们在某个村镇相遇,请示出Town,否则输出Road

样例输入1

5 2
1 2
2 3
3 4
4 5
1 3
1 5

样例输出1

Town
Town

样例输入2

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

样例输处2

Town
Road
Town
Town
Town
Town
Road
Road
Road

数据范围

$2 \leq n \leq 100000$

$1 \leq q \leq 100000$

对于每一个询问 $1 \leq c_{i} < d_{i} \leq n$