問題文

パソコン力を高めるの国は N 個の都市とそれらを結ぶ N - 1 本の双方向の道路からなる。道路 i は都市 A_i, B_i を結ぶ。道路以外を使って都市間を移動することはできず、またどの国からどの国へもいくつかの道路を通ることで移動することができる。つまり、この国はグラフとして木構造をなす。

パ研国も N 個の都市からなる。この国の都市 a, b \ (a \neq b) の間には、以下の条件を満たすとき、またそのときに限って道路が存在する。

• パソコン力を高めるの国の都市 a, b 間を K 本未満の道路を通って行き来できない。

以下の Q 個の質問に答えよ。i 番目の質問は以下である。

• パ研国の都市 X_i, Y_i の間を道路のみを用いて行き来できるか？もしできるならば、最低何本の道路を通る必要があるか？

制約

• 2 \leq K + 1 \leq N \leq 10^5
• 1 \leq A_i, B_i \leq N \ (1 \leq i \leq N - 1)
• 与えられるグラフは木である。
• 1 \leq Q \leq 10^5
• 1 \leq X_i, Y_i \leq N, X_i \neq Y_i \ (1 \leq i \leq N - 1)
• 入力は全て整数

配点

以下の小課題に点数が定められている。

1. (300 点) N, Q \leq 1000
2. (500 点) 追加の制約はない。

入力例 1

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

出力例 1

1
3

パソコン力を高めるの国における都市 1, 4 の距離は 3 なので、パ研国における都市 1, 4 の距離は 1 である。よって、クエリ 1 では 1 を出力すれば良い。

クエリ 2 については、都市 2, 4, 1, 3 の順に進むことで移動できる。これが最善なので、 3 を出力する。

入力例 2

7 3 3
1 2
1 3
2 4
2 5
3 6
3 7
3 4
2 3
6 7

出力例 2

1
3
2