题目背景

你像天外来物一样求之不得，你在世俗里的名字不重要了。

正好我隐藏的人格是契而不舍，直到蜂拥而至的人都透明了。

题目描述

ChA 在天上点缀了 $n$ 颗星星，编号为 $1 \sim n$。他们之间有 $n - 1$ 对星链。

Wa1 仰望星空，手指沿着星链移动，她发现星星构成了一棵树结构。

于是 Wa1 为每一颗星星附上了 $1\sim n$ 的编号。

“我要随便选两个数字 $l, r$，然后用手指把编号在 $[l,r]$ 的星星，两两沿着星链按最短路径连接。我手指划过的所有星星和星链就属于同一个星系。”

“简单地说，我要让这个星系包含编号在 $[l,r]$ 中的所有点并且连通。虽然有很多，但我只要满足条件的最小的星系。”

“这样生成的星系叫作 $[l,r]$ 的天外来物，即 $f(l,r)$。”

ChA 共 $q$ 次望向那片曾经的星空。他每次会随意想两个整数 $L_i,R_i$。他想知道有多少种不同的 $f(l,r)$，其中 $L_i\le l\le r\le R_i$。

称 $f$ 相同，当且仅当其包含的点集相同。

输入格式

第一行，两个整数 $n,q$，具体意义见题目描述。

接下来 $n-1$ 行，每行两个整数 $x,y$，表示一条星链连接的两颗星星。

接下来 $q$ 行，每行两个整数 $L_i,R_i$。

输出格式

共 $q$ 行，每行一个整数，表示满足 $L\le l\le r\le R$ 互不相同 $f(l,r)$ 的个数。

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

3
3
8
5
3

10 10
1 2
1 3
2 4
2 5
4 6
1 7
1 8
1 9
5 10
3 4
8 10
7 9
4 10
2 7
9 9
2 5
3 10
6 9
1 5

3
6
6
22
15
1
8
30
10
10

提示

【样例解释 #1】

以下是所有合法 $f(i,j)$ 的对应集合。

$f(1,1)=\{1\}$，$f(2,2)=\{2\}$，$f(3,3)=\{3\}$，$f(4,4)=\{4\}$，$f(5,5)=\{5\}$。

$f(1,2)=\{1,2\}$，$f(2,3)=\{2,3\}$，$f(3,4)=\{1,2,3,4\}$，$f(4,5)=\{1,2,4,5\}$。

$f(1,3)=\{1,2,3\}$，$f(2,4)=\{1,2,3,4\}$，$f(3,5)=\{1,2,3,4,5\}$。

$f(1,4)=\{1,2,3,4\}$，$f(2,5)=\{1,2,3,4,5\}$。

$f(1,5)=\{1,2,3,4,5\}$。

【样例解释 #2】

该样例满足测试点 $1, 2$ 的约束条件。

【样例 #3】

见选手目录下的 $\textbf{\textit{unearthed/unearthed3.in}}$ 与 $\textbf{\textit{unearthed/unearthed3.ans}}$。

该样例满足测试点 $1, 2$ 的约束条件。

【样例 #4】

见选手目录下的 $\textbf{\textit{unearthed/unearthed4.in}}$ 与 $\textbf{\textit{unearthed/unearthed4.ans}}$。

该样例满足测试点 $3, 4$ 的约束条件。

【样例 #5】

见选手目录下的 $\textbf{\textit{unearthed/unearthed5.in}}$ 与 $\textbf{\textit{unearthed/unearthed5.ans}}$。

该样例满足测试点 $5\sim 8$ 的约束条件。

【样例 #6】

见选手目录下的 $\textbf{\textit{unearthed/unearthed6.in}}$ 与 $\textbf{\textit{unearthed/unearthed6.ans}}$。

该样例满足测试点 $9\sim 11$ 的约束条件。

【样例 #7】

见选手目录下的 $\textbf{\textit{unearthed/unearthed7.in}}$ 与 $\textbf{\textit{unearthed/unearthed7.ans}}$。

该样例满足测试点 $12, 13$ 的约束条件。

【样例 #8】

见选手目录下的 $\textbf{\textit{unearthed/unearthed8.in}}$ 与 $\textbf{\textit{unearthed/unearthed8.ans}}$。

该样例满足测试点 $14, 15$ 的约束条件。

【样例 #9】

见选手目录下的 $\textbf{\textit{unearthed/unearthed9.in}}$ 与 $\textbf{\textit{unearthed/unearthed9.ans}}$。

该样例满足测试点 $16\sim 19$ 的约束条件。

【样例 #10】

见选手目录下的 $\textbf{\textit{unearthed/unearthed10.in}}$ 与 $\textbf{\textit{unearthed/unearthed10.ans}}$。

该样例满足测试点 $20\sim 25$ 的约束条件。

【数据范围】

本题共 $25$ 个测试点，每个 $4$ 分。

对于所有测试数据，保证：

• $1\le n,q\le 5\times 10^5$；
• $1\le L_i\le R_i\le n$；
• $1\le x,y\le n$，保证输入的边构成树。

::cute-table{tuack} |测试点编号|$n,q \le$|特殊性质| |:--:|:--:|:--:| |$1, 2$|$100$|无| |$3, 4$|$600$|^| |$5\sim 8$|$5000$|^| |$9\sim 11$|$5\times 10^5$|A| |$12, 13$|^|B| |$14, 15$|^|C| |$16\sim 19$|$10^5$|无| |$20\sim 25$|$5\times 10^5$|^|

特殊性质 A：$q = 1$。
特殊性质 B：对于所有 $2 \le i \le n$，均有 $i$ 与 $i-1$ 连边。
特殊性质 C：对于所有 $2 \le i \le n$，均有 $i$ 与 $1$ 连边。