AT_aalc001_v 連結性 2

頂点に $ 1 $ から $ N $ の番号が付いた $ N $ 頂点の木があります。 $ i $ 番目の辺は頂点 $ u_i $ と頂点 $ v_i $ を結んでいます。 整数の区間 $ [a,b] $ が **good** であるとは、頂点 $ a,a+1,\ldots,b $ からなる誘導部分グラフが 連結であることをいいます。 クエリを $ Q $ 個処理してください。 $ i $ 番目のクエリでは整数 $ L_i,R_i $ が与えられるので、 次の条件をともに満たす整数の組 $ (a,b) $ の個数を求めてください。 - $ L_i \leq a \leq b \leq R_i $ - 区間 $ [a,b] $ は good である

入力は以下の形式で標準入力から与えられる。 > $ N $ $ Q $ $ u_1 $ $ v_1 $ $ u_2 $ $ v_2 $ $ \vdots $ $ u_{N-1} $ $ v_{N-1} $ $ L_1 $ $ R_1 $ $ L_2 $ $ R_2 $ $ \vdots $ $ L_Q $ $ R_Q $

$ Q $ 行出力せよ。 $ i $ 行目には、 $ i $ 番目のクエリに対する答えを出力せよ。

### Sample Explanation 1 good な区間は以下の $ 9 $ 個です。 $ [1,1], [1,5], [2,2], [2,5], [3,3], [3,5], [4,4], [4,5], [5,5] $ ### Constraints - $ 1 \leq N \leq 2 \times 10^5 $ - $ 1 \leq Q \leq 2 \times 10^5 $ - $ 1 \leq u_i \lt v_i \leq N $ - 与えられるグラフは木 - $ 1 \leq L_i \leq R_i \leq N $ - 入力される数値はすべて整数