树（tree）

题目描述

小 B 在复习数据结构，他给了你一棵树，根节点为 $1$，总共有 $n$ 个节点。

他想要跟你玩一个游戏，每次小 B 先给出一个区间 $[l,r]$，只关心 $[l,r]$ 内部所有点在树上的最小连通块，即提取出 $[l,r]$ 的虚树。

然后你可以随机选择一个 $[l,r]$ 的虚树内部的点，如果选到的点在虚树上的子树有完美匹配，那么你获胜，否则小 B 获胜。

游戏一定有 $q$ 轮，每轮的 $l,r$ 是不同的，你需要求出你获胜的概率乘上 $[l,r]$ 虚树大小后的结果，可以证明该答案一定为整数。

输入格式

从文件 tree.in 中读入数据。

第一行两个整数 $n,q$，表示树上节点的数量和询问的数量。

接下来 $n-1$ 行，每行两个整数 $x,y$ 表示树上的一条边。

接下来 $q$ 行每行两个整数 $l,r$ 表示询问的区间。

输出格式

输出到文件 tree.out 中。

共 $q$ 行，每行一个整数表示答案。

样例 1 输入

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

样例 1 输出

1
1
2
2
3

样例 1 解释

对于第三组询问，虚树内的点包含 $\{1,2,3,4\}$，其子树中具有完美匹配的点有 $\{1,2\}$。

附加样例

见下发文件中的对应文件。

数据范围

对于所有数据，保证 $1\le n\le 2\times10^5$，$1\le q\le 7\times10^4$，$1\le x,y\le n$，$1\le l\le r\le n$。