#P1111. 城镇道路判定

城镇道路判定

题目描述

远行公会维护着一套由 NN 个驿站组成的地下通道系统。任意两个驿站之间都恰好有一条简单路线相连,因此这套系统可以看作一棵树。

公会把一条路线按边数的奇偶性分成两类:

  • 若从一个驿站走到另一个驿站需要经过偶数条通道,则称两端处于同类区域;
  • 若需要经过奇数条通道,则称两端处于异类区域。

现在给出 QQ 组驿站对,请你判断每一组属于哪一类。若路线长度为偶数,输出 Town;若路线长度为奇数,输出 Road

输入格式

第一行输入两个整数 N,QN,Q,分别表示驿站数量和询问数量。

接下来 N1N-1 行,每行输入两个整数 ai,bia_i,b_i,表示驿站 aia_ibib_i 之间有一条通道。

最后 QQ 行,每行输入两个整数 ci,dic_i,d_i,表示需要判断的一对驿站。

输出格式

对每个询问输出一行。若两点之间的路线长度为偶数,输出 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

样例说明

2266 的路线为 213562\to1\to3\to5\to6,长度为 44,所以输出 Town

数据范围

  • 对于 30%30\% 的数据,N1000N\le 1000
  • 对于 100%100\% 的数据,2N1052\le N\le 10^51Q1051\le Q\le 10^5,输入的边构成一棵树,1ci,diN1\le c_i,d_i\le N