AT_aalc001_v.Connectivity 2

有一棵包含 $N$ 个顶点的树，顶点编号为 $1$ 到 $N$。第 $i$ 条边连接顶点 $u_i$ 和 $v_i$。

若由顶点 $a, a+1, \ldots, b$ 诱导出的子图是连通的，则整数区间 $[a,b]$ 被称为好区间。

你需要处理 $Q$ 个查询。在第 $i$ 个查询中，给定整数 $L_i, R_i$。请找出满足以下两个条件的整数对 $(a,b)$ 的数量：

• $L_i \leq a \leq b \leq R_i$
• 区间 $[a,b]$ 是好区间。

输入从标准输入中按以下格式给出：

$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$ 个查询的答案。

样例 1 解释：
以下 $9$ 个区间是“好”的：

$[1,1], [1,5], [2,2], [2,5], [3,3], [3,5], [4,4], [4,5], [5,5]$

约束条件

• $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$
• 输入中的所有数值均为整数。