AT_pakencamp_2023_day2_h Two PCities

パソコン力を高めるの国は $ N $ 個の都市とそれらを結ぶ $ N - 1 $ 本の双方向の道路からなる。道路 $ i $ は都市 $ A_i, B_i $ を結ぶ。道路以外を使って都市間を移動することはできず、またどの国からどの国へもいくつかの道路を通ることで移動することができる。つまり、この国はグラフとして木構造をなす。 パ研国も $ N $ 個の都市からなる。この国の都市 $ a, b \ (a \neq b) $ の間には、以下の条件を満たすとき、またそのときに限って道路が存在する。 - パソコン力を高めるの国の都市 $ a, b $ 間を $ K $ 本未満の道路を通って行き来できない。 以下の $ Q $ 個の質問に答えよ。 $ i $ 番目の質問は以下である。 - パ研国の都市 $ X_i, Y_i $ の間を道路のみを用いて行き来できるか？もしできるならば、最低何本の道路を通る必要があるか？

入力は以下の形式で標準入力から与えられる。 > $ N $ $ Q $ $ K $ $ A_1 $ $ B_1 $ $ A_2 $ $ B_2 $ $ \vdots $ $ A_{N-1} $ $ B_{N-1} $ $ X_1 $ $ Y_1 $ $ X_2 $ $ Y_2 $ $ \vdots $ $ X_Q $ $ Y_Q $

$ Q $ 行出力せよ。 $ i \ (1 \leq i \leq Q) $ 行目には質問 $ i $ への答えを出力せよ。各質問では、もし行き来ができない場合 `-1` を出力し、そうでない場合必要な道路の最小本数を出力せよ。

### 配点 以下の小課題に点数が定められている。 1. ( $ 300 $ 点) $ N, Q \leq 1000 $ 2. ( $ 500 $ 点) 追加の制約はない。 ### Sample Explanation 1 パソコン力を高めるの国における都市 $ 1, 4 $ の距離は $ 3 $ なので、パ研国における都市 $ 1, 4 $ の距離は $ 1 $ である。よって、クエリ $ 1 $ では `1` を出力すれば良い。 クエリ $ 2 $ については、都市 $ 2, 4, 1, 3 $ の順に進むことで移動できる。これが最善なので、 `3` を出力する。 ### Constraints - $ 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) $ - 入力は全て整数