579. 树上定向

QQ小方以前不会做”唐纳德先生与网络降级计划“，现在他会了，所以他急切的想教会你。

选一个根，使得若干祖先和孩子的关系成立。

考虑任选一个为根，然后那些关系就是若干树上的路径。考虑 $s$ 到 $t$ 。

• 如果 $t$ 是 $s$ 的祖先，说明根应该在 $t$ 的子树外面。
• 否则，根应该在 $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$ 取模以后的答案。