D - Collision Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 400 点

問題文

高橋王国は 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 を目指して同じ速さで移動するとき、二人が街で出会うか道路上（両端の街を除く）で出会うかを判定せよ。ただし、二人とも最短経路で移動し、街の中を移動する時間は無視できるものとする。

制約

  • 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)
  • 入力は全て整数
  • どの街からどの街へもいくつかの道路を通ることで移動できる

入力

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

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 と出力せよ。

入力例 1

4 1
1 2
2 3
2 4
1 2

出力例 1

Road

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

入力例 2

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

出力例 2

Town
Town

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

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

入力例 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

Score : 400 points

Problem Statement

The Kingdom of Takahashi is made up of N towns and N-1 roads, where the towns are numbered 1 through N. The i-th road (1 \leq i \leq N-1) connects Town a_i and Town b_i, so that you can get from every town to every town by using some roads. All the roads have the same length.

You will be given Q queries. In the i-th query (1 \leq i \leq Q), given integers c_i and d_i, solve the following problem:

  • Takahashi is now at Town c_i and Aoki is now at Town d_i. They will leave the towns simultaneously and start traveling at the same speed, Takahashi heading to Town d_i and Aoki heading to Town c_i. Determine whether they will meet at a town or halfway along a road. Here, assume that both of them travel along the shortest paths, and the time it takes to pass towns is negligible.

Constraints

  • 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)
  • All values in input are integers.
  • It is possible to get from every town to every town by using some roads.

Input

Input is given from Standard Input in the following format:

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

Output

Print Q lines. The i-th line (1 \leq i \leq Q) should contain Town if Takahashi and Aoki will meet at a town in the i-th query, and Road if they meet halfway along a road in that query.

Sample Input 1

4 1
1 2
2 3
2 4
1 2

Sample Output 1

Road

In the first and only query, Takahashi and Aoki simultaneously leave Town 1 and Town 2, respectively, and they will meet halfway along the 1-st road, so we should print Road.

Sample Input 2

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

Sample Output 2

Town
Town

In the first query, Takahashi and Aoki simultaneously leave Town 1 and Town 3, respectively, and they will meet at Town 2, so we should print Town.

In the first query, Takahashi and Aoki simultaneously leave Town 1 and Town 5, respectively, and they will meet at Town 3, so we should print Town.

Sample Input 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

Sample Output 3

Town
Road
Town
Town
Town
Town
Road
Road
Road