题目描述

某检索系统使用一棵 Splay 树维护 $n$ 个索引结点。结点编号为 $1,2,\ldots,n$。

为了让刚刚访问的索引结点更容易再次被访问，当系统收到对结点 $x$ 的请求时，会执行一次 $Splay(x)$：不断对结点 $x$ 进行旋转，直到将它移动到整棵树的根。

下面介绍 $Splay$ 操作所使用的三类调整。设 $p$ 是 $x$ 的父结点，$g$ 是 $p$ 的父结点；$A,B,C,D$ 均表示可能为空的子树。下图中的结构均以“左孩子画在左侧、右孩子画在右侧”的方式表示。

1. Zig

当 $p$ 已经是根时，只需旋转 $x$ 一次。

以下给出 $x$ 是 $p$ 左孩子时的结构变化；右孩子的情况与之对称。

旋转前：

        p
       / \
      x   C
     / \
    A   B

旋转后：

        x
       / \
      A   p
         / \
        B   C

2. Zig-zig

当 $p$ 不是根，并且 $x$ 与 $p$ 同为各自父结点的左孩子，或同为右孩子时，先旋转 $p$，再旋转 $x$。

下面给出“左—左”情形；“右—右”情形与之对称。

初始结构：

          g
         / \
        p   D
       / \
      x   C
     / \
    A   B

第一次旋转 $p$ 后：

          p
         / \
        x   g
       / \ / \
      A  B C  D

第二次旋转 $x$ 后：

          x
         / \
        A   p
           / \
          B   g
             / \
            C   D

3. Zig-zag

当 $p$ 不是根，并且 $x$ 与 $p$ 分别是左孩子和右孩子时，连续旋转 $x$ 两次。

下面给出“左—右”情形；“右—左”情形与之对称。

初始结构：

          g
         / \
        p   D
       / \
      A   x
         / \
        B   C

第一次旋转 $x$ 后：

          g
         / \
        x   D
       / \
      p   C
     / \
    A   B

第二次旋转 $x$ 后：

          x
         / \
        p   g
       / \ / \
      A  B C  D

一次普通旋转可以形式化描述如下。设 $fa_x$ 为 $x$ 的父结点，$ls$ 和 $rs$ 分别表示 $x$ 的左、右子结点：

• 若 $x$ 是 $fa_x$ 的左孩子，则令 $rs$ 成为 $fa_x$ 的左孩子，并令 $fa_x$ 成为 $x$ 的右孩子；
• 若 $x$ 是 $fa_x$ 的右孩子，则令 $ls$ 成为 $fa_x$ 的右孩子，并令 $fa_x$ 成为 $x$ 的左孩子。

定义一个结点的访问层级为它在树中的深度，其中根结点深度为 $0$。

系统会在 $n$ 个结点中等概率随机选择一个结点 $y$，并执行 $Splay(y)$。

对于每个结点 $x$，请计算执行操作后结点 $x$ 的期望访问层级。

输入格式

第一行包含一个正整数 $n$，表示树中结点的数量。

接下来 $n$ 行，每行包含两个非负整数。

第 $i$ 行的两个整数分别表示结点 $i$ 的左孩子编号和右孩子编号；若某个编号为 $0$，表示对应的孩子不存在。

保证结点 $1$ 是初始树的根。

输出格式

输出共 $n$ 行。

第 $i$ 行输出：随机选择结点 $y$ 并执行 $Splay(y)$ 后，结点 $i$ 的期望访问层级乘以 $n$，再对 $10^9+7$ 取模的结果。

样例

样例输入

5
2 5
3 4
0 0
0 0
0 0

样例输出

5
5
8
10
8

样例解释

初始树为：

        1
       / \
      2   5
     / \
    3   4

分别执行 $Splay(1),Splay(2),\ldots,Splay(5)$ 后，树的结构如下。

执行 $Splay(1)$ 后

        1
       / \
      2   5
     / \
    3   4

执行 $Splay(2)$ 后

        2
       / \
      3   1
         / \
        4   5

执行 $Splay(3)$ 后

    3
     \
      2
       \
        1
       / \
      4   5

执行 $Splay(4)$ 后

        4
       / \
      2   1
     /     \
    3       5

执行 $Splay(5)$ 后

        5
       /
      1
     /
    2
   / \
  3   4

例如，结点 $1$ 在上述五棵树中的深度依次为 $0,1,2,1,1$，深度之和为 $5$。因此它的期望深度为 $\frac{5}{5}$，题目要求输出期望值乘以 $n=5$，故第一行输出 $5$。

数据范围与提示

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

$$1\le n\le 10^6.$$

原题中的测试点信息图已整理为下表：

测试点编号	$n\le$	特殊限制
$1\sim 8$	$2000$	无
$9\sim 10$	$2\times 10^5$	A
$11\sim 13$	$10^5$	B
$14\sim 16$		C
$17\sim 19$		无
$20\sim 22$	$5\times 10^5$
$23\sim 25$	$10^6$

特殊限制 A：二叉树为满二叉树。

特殊限制 B：所有结点均没有右孩子。

特殊限制 C：所有结点均至多只有一个孩子。