Welcome Contest （京都・オープン） 2026/03/26 14:00 ~ 2026/03/26 18:00 4:00:00.000

J Tree Paths

問題
制限時間: 2 sec メモリ制限: 1024 MB
Tree Paths
Statement

頂点 \(1,\) 頂点 \(2,\) \(\dots,\) 頂点 \(N\) の \(N\) 頂点の木 \(T\) が与えられます。 \(i\) 番目 \((1 \leq i \leq N-1)\) の辺は頂点 \(u_i\) と頂点 \(v_i\) を双方向に結びます．

任意の \(2\) 頂点 \(u, v\) に対して、 \(P(u, v)\) を \(T\) 上の \(u-v\) 間の最短パスの頂点集合、 \(d(u, v)\) を \(T\) 上の \(u-v\) 間の最短距離とします。

以下の \(Q\) 個のクエリに答えて下さい．

  • \(s_1, t_1, s_2, t_2\) : \(s_1\) - \(t_1\) パスと \(s_2\) - \(t_2\) パス間の距離を出力せよ．
    • \(s_1\) - \(t_1\) パスと \(s_2\) - \(t_2\) パス間の距離は，任意の頂点 \(x\) \(\in\) \(P(s_1, t_1)\), \(y\) \(\in\) \(P(s_2, t_2)\) に対する\(d(x, y)\) の内，最小の値として定義します．

Input

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

\(N~Q\)
\(u_1~v_1\)
\(u_2~v_2\)
\(\vdots\)
\(u_{N-1}~v_{N-1}\)
\(query_1\)
\(query_2\)
\(\vdots\)
\(query_Q\)

ここで\(query_i\)は\(i\)番目のクエリであり、以下の形式であたえられます。

\(s_1~t_1~s_2~t_2\)

入力は以下の制約をすべて満たします。

  • \(2\leq N\leq 10^5\)
  • \(1\leq Q\leq 10^5\)
  • \(1\leq u_i \lt v_i \leq N\)
  • \(1\leq s_1 \lt t_1 \leq N\)
  • \(1\leq s_2 \lt t_2 \leq N\)
  • 入力はすべて整数

Output

\(Q\) 個のクエリを処理してください．

Examples

Input 1
5 3
1 4
2 4
1 3
2 5
3 5 2 4
1 3 2 5
1 4 2 5
Output 1
0
2
1
Input 2
7 3
1 2
1 3
2 4
2 5
3 6
3 7
4 5 6 7
1 4 3 7
3 4 6 7
Output 2
2
1
0

サンプル