Person in Charge

• SleepingCup

Problem Description

Given a binary tree with $4n - 1$ nodes, where each non-leaf node has exactly two children. The non-leaf nodes are numbered from $1$ to $2n - 1$, and the leaf nodes are numbered from $2n$ to $4n - 1$. Initially, there are no numbers on any leaf nodes.

A DFS traversal is defined as elegant if and only if, when concatenating the numbers on all labeled leaf nodes in the order of the DFS traversal, the resulting sequence can be reduced to an empty sequence by repeatedly eliminating adjacent identical numbers. For example, in the figure below, if leaf nodes $4$ and $6$ are labeled with $1$, and leaf nodes $5$ and $7$ are labeled with $2$, then the sequence formed by the DFS traversal $[1, 4, 2, 7, 3, 5, 6]$ is $[1, 2, 2, 1]$. This sequence can be reduced to $[1, 1]$ by eliminating the adjacent $2$s, and further to an empty sequence by eliminating the adjacent $1$s, so this DFS traversal is elegant. On the other hand, the DFS traversal $[1, 4, 2, 3, 5, 6, 7]$ produces the sequence $[1, 2, 1, 2]$, which cannot be reduced to an empty sequence by eliminating adjacent identical numbers, so this DFS traversal is not elegant.

Given $n$ operations, the $i$-th ($1 \le i \le n$) operation selects two unlabeled leaf nodes and labels them with the number $i$. It is guaranteed that after each operation, there exists at least one elegant DFS traversal. You need to determine the number of elegant DFS traversals after each operation. Since the answer may be large, you only need to output the result modulo $1,000,000,007$.

Input Format

The first line of input contains a non-negative integer $c$, representing the test case number. $c = 0$ indicates that the test case is a sample.

The second line of input contains a positive integer $n$, indicating that the binary tree has $4n - 1$ nodes.

The $(i + 2)$-th line ($1 \le i \le 2n - 1$) contains two positive integers $l_i$ and $r_i$, representing the left and right children of node $i$, respectively. It is guaranteed that $i < l_i, r_i \le 4n - 1$, and all $l_i$ and $r_i$ are distinct.

The $(i + 2n - 1)$-th line ($1 \le i \le n$) contains two positive integers $a_i$ and $b_i$, representing the leaf nodes selected in the $i$-th operation. It is guaranteed that $2n \le a_i, b_i \le 4n - 1$, and all $a_i$ and $b_i$ are distinct.

Output Format

Output $n$ lines, where the $i$-th line ($1 \le i \le n$) contains a non-negative integer representing the number of elegant DFS traversals after the $i$-th operation, modulo $1,000,000,007$.

Samples

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

8
4

0
6
2 3
4 21
22 23
5 11
6 8
7 9
12 13
10 18
14 15
16 17
19 20
12 13
14 15
16 19
17 18
20 21
22 23

2048
2048
2048
1024
512
512

Sample 1 Explanation

This sample corresponds to the example in the Problem Description.

• After the first operation, leaf nodes $4$ and $6$ are labeled with $1$, and leaf nodes $5$ and $7$ are unlabeled. The sequence formed by any DFS traversal is $[1, 1]$, so all $2^3 = 8$ DFS traversals are elegant.
• After the second operation, leaf nodes $4 \sim 7$ are labeled with $1, 2, 1, 2$, respectively. There are $4$ elegant DFS traversals: $[1, 4, 2, 3, 6, 5, 7], [1, 4, 2, 7, 3, 5, 6], [1, 2, 3, 6, 5, 7, 4], [1, 2, 7, 3, 5, 6, 4]$.

Sample 2

See the files tree/tree2.in and tree/tree2.ans in the contestant directory.

This sample satisfies the constraints of test cases $6 \sim 10$.

Sample 3

See the files tree/tree3.in and tree/tree3.ans in the contestant directory.

This sample satisfies the constraints of test cases $11, 12$.

Sample 4

See the files tree/tree4.in and tree/tree4.ans in the contestant directory.

This sample satisfies the constraints of test cases $17 \sim 20$.

Sample 5

See the files tree/tree5.in and tree/tree5.ans in the contestant directory.

This sample satisfies the constraints of test cases $24, 25$.

Data Range

For all test data, the following guarantees hold:

• $1 \le n \le 2 \times 10^5$;
• For all $1 \le i \le 2n - 1$, $i < l_i, r_i \le 4n - 1$, and all $l_i$ and $r_i$ are distinct;
• For all $1 \le i \le n$, $2n \le a_i, b_i \le 4n - 1$, and all $a_i$ and $b_i$ are distinct;
• After each operation, there exists at least one elegant DFS traversal.

• Special Property A: The two leaf nodes selected in each operation are in different subtrees of node $1$.
• Special Property B: There exists a non-negative integer $m$ such that $n = 2^m$, and for all $1 \le i \le 2n - 1$, $l_i = 2i$ and $r_i = 2i + 1$.