4 人解决，13 人已尝试。
4 份提交通过，共有 32 份提交。
8.8 EMB 奖励。
单点时限: 6.0 sec
内存限制: 1024 MB
QQ小方以前不会做”唐纳德先生与网络降级计划“，现在他会了，所以他急切的想教会你。
选一个根，使得若干祖先和孩子的关系成立。
考虑任选一个为根，然后那些关系就是若干树上的路径。考虑 $s$ 到 $t$ 。
题目保证有解，我们只要把解的范围缩小就可以了。对于「在子树外面」的那些约束，我们大可以无视，最后选答案的时候选一个深度最小的就可以了；而对于在子树里面的那些约束，就更好办了，维护一个最大的历史深度就好了。实现的时候可以合二为一，直接维护答案。
（这明明是 ultmaster 写的 $1$ 月题解嘛。）
单单讲给你听肯定是不够的，为了表现自己，QQ小方现在要考考你。
QQ小方将题目升级了。简单来说，QQ小方会给你一棵包含 $n$ 个节点的树，并且会给你 $q$ 个无序对 $(s_i, t_i)$ ，你需要将这棵树中的 $n-1$ 条边进行定向，即对于一条边 $(u_i, v_i)$ ，你需要决定这条边是由 $u_i$ 指向 $v_i$ 或者 $v_i$ 指向 $u_i$ 。在进行全部的定位以后，得到的这棵树需要满足对于所有的无序对至少存在一条可行路径，即要么 $s_i$ 能到达 $t_i$ 、要么 $t_i$ 能到达 $s_i$ 。而现在，QQ小方想知道可行的定位方案数量。可行的定位方案数量可能很大，你只需要输出对 $10^9+7$ 取模以后的答案。
第一行一个整数 $t$ ($1 \le t \le 10^5$)，表示数据组数。
对于每组数据，首先有一行两个整数 $n, q$ ($2 \le n \le 10^6$, $1 \le q \le 10^6$)。
接下来 $n-1$ 行，第 $i$ 行两个整数 $u_i, v_i$ ($1 \le u_i, v_i \le n$, $u_i \ne v_i$) 表示 $u_i$ 和 $v_i$ 之间有一条无向边。保证无序对 $(u_i, v_i)$ 在同组数据中至多出现一次。
接下来 $q$ 行，第 $i$ 行两个整数 $s_i, t_i$ ($1 \le s_i, t_i \le n$, $s_i \ne t_i$)。无序对 $(s_i, t_i)$ 可能出现多次。
输入保证所有测试数据的 $\Sigma n, \Sigma q$ 不超过 $10^6$。
对于每组数据，输出一个整数表示答案。
2 4 1 1 2 2 3 3 4 2 4 4 3 1 2 1 3 1 4 2 3 2 4 3 4
4 0
4 人解决，13 人已尝试。
4 份提交通过，共有 32 份提交。
8.8 EMB 奖励。