AT_abc209_d [ABC209D] Collision

题目描述

给出一张 $n$ 点 $(n-1)$ 边的无向图，第 $i$ 条边连接点 $a_i$ 和点 $b_i$，长度为 $1$。

给出 $q$ 个询问。第 $i$ 个询问给出两个点 $c_i$ 和 $d_i$。请求出两点之间的最短路长度，若为奇数请输出Road，若为偶数请输出Town。保证图联通。

输入格式

第一行输入点数 $n$ 和询问次数 $q$。

第二行到第 $n$ 行，第 $(i-1)$ 行输入两个数 $a_i,b_i$，表示第 $i$ 条边连接的两个点。

从第 $(n+1)$ 起的 $q$ 行，第 $i$ 行输入两个数 $c_i,d_i$，表示第 $i$ 次询问的两个点。

输出格式

无

输入输出样例 #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 解释

很明显给出的图为一条链（1-2-3-4-5）。$1$ 和 $3$ 之间的最短路长度为 $2$，$1$ 和 $5$ 之间的最短路长度为 $4$。它们都是偶数，所以都输出Town。

数据规模与约定

对于 $100\%$ 的数据，保证：

• 输入的数值均为整数；
• $2\le n\le 10^5$，$1\le q \le 10^5$；
• $1\le a_i,b_i,c_i,d_i\le n$，且对于同一个 $i$，都有 $a_i\lt b_i$，$c_i\lt d_i$。