题目描述

给定一棵 $4n - 1$ 个结点的二叉树，其中每个非叶结点都有恰好两个子结点。非叶结点编号为 $1$ 到 $2n - 1$，叶子结点编号为 $2n$ 到 $4n - 1$。初始时，每个叶子结点上都没有数字。

定义一个 DFS 序是优美的，当且仅当按该 DFS 序将所有标有数字的叶子结点上的数字拼成一个序列时，该序列可以通过若干次消除相邻相同数字的方式得到空序列。

给定 $n$ 次操作，第 $i$（$1 \leq i \leq n$）次操作会选择两个没有数字的叶子结点，然后将这两个结点标上数字 $i$。保证在每次操作后，存在至少一个优美的 DFS 序。要求出每次操作后的优美的 DFS 序的数量，答案对 $10^9 + 7$ 取模。

输入格式

1. 第一行包含一个非负整数 $c$，表示测试点编号，$c = 0$ 表示该测试点为样例。
2. 第二行包含一个正整数 $n$，表示二叉树的结点个数为 $4n - 1$。
3. 第 $i + 2$（$1 \leq i \leq 2n - 1$）行包含两个正整数 $l_i$ 和 $r_i$，分别表示结点 $i$ 的左右子结点。保证 $i < l_i$，$r_i \leq 4n - 1$，且所有的 $l_i, r_i$ 互不相同。
4. 第 $i + 2n + 1$（$1 \leq i \leq n$）行包含两个正整数 $a_i, b_i$，表示第 $i$ 次操作选择的叶子结点的编号。保证 $2n \leq a_i, b_i \leq 4n - 1$，且所有的 $a_i, b_i$ 互不相同。

输出格式

输出 $n$ 行，其中第 $i$（$1 \leq i \leq n$）行包含一个非负整数，表示第 $i$ 次操作后的优美的 DFS 序的数量对 $10^9 + 7$ 取模后的结果。

样例1

输入

0
2
2 3
4 7
5 6
4 6
5 7

输出

8
4

样例1解释

• 第一次操作后，叶子结点 $4$ 和 $6$ 标有数字 $1$，拼成的序列均为 $[1, 1]$，所有 $2^3 = 8$ 个 DFS 序都是优美的。
• 第二次操作后，叶子结点 $4 \sim 7$ 分别标有数字 $1, 2, 1, 2$，共有 $4$ 个优美的 DFS 序。

数据范围

• $1 \leq n \leq 2 \times 10^5$。
• 对于所有 $1 \leq i \leq 2n - 1$，$i < l_i$，$r_i \leq 4n - 1$，且所有的 $l_i, r_i$ 互不相同。
• 对于所有 $1 \leq i \leq n$，$2n \leq a_i, b_i \leq 4n - 1$，且所有的 $a_i, b_i$ 互不相同。
• 每次操作后，存在至少一个优美的 DFS 序。

特殊性质说明：

• A：保证每次操作选择的两个叶子结点位于结点 $1$ 的不同子树内。
• B：保证存在非负整数 $m$ 满足 $n = 2^m$，且对于所有 $1 \leq i \leq 2n - 1$，均有 $l_i = 2i$，$r_i = 2i + 1$。