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$ 次询问的两个点。
输出格式
$ Q $ 行出力せよ。 $ i\,\ (1\ \leq\ i\ \leq\ Q) $ 行目には、$ i $ 番目のクエリにおいて二人が街で出会うなら `Town`、道路上で出会うなら `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$。