#abc209d. [abc209_d]Collision

[abc209_d]Collision

問題文

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

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

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

制約

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

入力

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

NN QQ a1a_1 b1b_1 a2a_2 b2b_2 hspace0.6cmvdots\\hspace{0.6cm}\\vdots aN1a_{N-1} bN1b_{N-1} c1c_1 d1d_1 c2c_2 d2d_2 hspace0.6cmvdots\\hspace{0.6cm}\\vdots cQc_Q dQd_Q

出力

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


入力例 1

4 1
1 2
2 3
2 4
1 2

出力例 1

Road

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


入力例 2

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

出力例 2

Town
Town

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

22 番目のクエリでは、高橋君は街 11、青木君は街 55 を同時に出発し、街 33 で出会います。よって 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