#P1111. 城镇道路判定
城镇道路判定
题目描述
远行公会维护着一套由 个驿站组成的地下通道系统。任意两个驿站之间都恰好有一条简单路线相连,因此这套系统可以看作一棵树。
公会把一条路线按边数的奇偶性分成两类:
- 若从一个驿站走到另一个驿站需要经过偶数条通道,则称两端处于同类区域;
- 若需要经过奇数条通道,则称两端处于异类区域。
现在给出 组驿站对,请你判断每一组属于哪一类。若路线长度为偶数,输出 Town;若路线长度为奇数,输出 Road。
输入格式
第一行输入两个整数 ,分别表示驿站数量和询问数量。
接下来 行,每行输入两个整数 ,表示驿站 与 之间有一条通道。
最后 行,每行输入两个整数 ,表示需要判断的一对驿站。
输出格式
对每个询问输出一行。若两点之间的路线长度为偶数,输出 Town;否则输出 Road。
样例
6 5
1 2
1 3
3 4
3 5
5 6
1 2
2 4
4 6
2 6
3 3
Road
Road
Road
Town
Town
样例说明
从 到 的路线为 ,长度为 ,所以输出 Town。
数据范围
- 对于 的数据,。
- 对于 的数据,,,输入的边构成一棵树,。