题目描述

高橋王国は $N$ 個の街と $N-1$ 本の道路からなり、街には $1$ から $N$ の番号がついています。また、$i\,\ (1\ \leq\ i\ \leq\ N-1)$ 本目の道路は街 $a_i$ と街 $b_i$ を双方向に結んでおり、どの街からどの街へもいくつかの道路を通ることで移動できます。道路は全て同じ長さです。

$Q$ 個のクエリが与えられます。$i\,\ (1\ \leq\ i\ \leq\ Q)$ 番目のクエリでは整数 $c_i,d_i$ が与えられるので、以下の問題を解いてください。

• 現在高橋君は街 $c_i$ に、青木君は街 $d_i$ にいる。二人が同時に街を出発し、それぞれ街 $d_i$, $c_i$ を目指して同じ速さで移動するとき、二人が街で出会うか道路上（両端の街を除く）で出会うかを判定せよ。ただし、二人とも最短経路で移動し、街の中を移動する時間は無視できるものとする。

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $Q$ $a_1$ $b_1$ $a_2$ $b_2$ $\hspace{0.6cm}\vdots$ $a_{N-1}$ $b_{N-1}$ $c_1$ $d_1$ $c_2$ $d_2$ $\hspace{0.6cm}\vdots$ $c_Q$ $d_Q$

输出格式

$Q$ 行出力せよ。 $i\,\ (1\ \leq\ i\ \leq\ Q)$ 行目には、$i$ 番目のクエリにおいて二人が街で出会うなら Town、道路上で出会うなら Road と出力せよ。

题目大意

题目描述

给出一张 $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$ 行。

说明/提示

样例 #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$。

4 1
1 2
2 3
2 4
1 2

Road

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

Town
Town

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

Town
Road
Town
Town
Town
Town
Road
Road
Road

提示

制約

• $2\ \leq\ N\ \leq\ 10^5$
• $1\ \leq\ Q\ \leq\ 10^5$
• $ 1\ \leq\ a_i\ <\ b_i\ \leq\ N\,\ (1\ \leq\ i\ \leq\ N-1) $
• $ 1\ \leq\ c_i\ <\ d_i\ \leq\ N\,\ (1\ \leq\ i\ \leq\ Q) $
• 入力は全て整数
• どの街からどの街へもいくつかの道路を通ることで移動できる

Sample Explanation 1

$1$ 番目のクエリでは、高橋君は街 $1$、青木君は街 $2$ を同時に出発し、$1$ 本目の道路上で出会います。よって Road と出力してください。

Sample Explanation 2

$1$ 番目のクエリでは、高橋君は街 $1$、青木君は街 $3$ を同時に出発し、街 $2$ で出会います。よって Town と出力してください。 $2$ 番目のクエリでは、高橋君は街 $1$、青木君は街 $5$ を同時に出発し、街 $3$ で出会います。よって Town と出力してください。