{"raw_statement":[{"iden":"statement","content":"Once upon a time, Mr. Cool created a tree (an undirected graph without cycles) of $n$ vertices, by assigning to each vertex $i > 1$ two numbers: $p_i < i$ — the direct ancestor of vertex $i$ and $w_i$ — the weight of the edge between vertex $i$ and $p_i$. Vertex $1$ is the root, so it does not have any ancestors. \n\nYou wanted to know what tree did Mr. Cool build, but Mr. Cool refused to tell this, but he gave you a tip:\n\nHe wrote all these numbers in one line. That's how he got array $b$ of length $2 dot.op n -2$.\n\nThen he randomly shuffled it. That's how he got array $a$, and Mr. Cool presented you with it.\n\nSince it is impossible to restore the tree knowing only values of array $a$, you decided to solve a different problem.\n\nLet's call a tree _k-long_, if there are exactly $k$ edges on the path between vertex $1$ and $n$.\n\nLet's call a tree _k-perfect_, if it is $k$-long and the sum of the weights of the edges on the path between vertex $1$ and vertex $n$ is maximal among all possible $k$-long trees that Mr. Cool could build.\n\nYour task is to print the sum of the weights of the edges on the path between vertex $1$ and vertex $n$ for all possible $k$-perfect trees or print $-1$ if a certain $k$-long tree could not be built by Mr. Cool.\n\nThe first line contains one integer $n$ ($2 <= n <= 10^5$) — the number of the vertices in the tree.\n\nThe second line contains $2 dot.op n -2$ integers $a_1, a_2, \\\\dots, a_{2 n -2} (1 <= a_i <= n -1)$ — the elements of array $a$. \n\nIn one line, print $n -1$ space-separated integers $w_1, w_2, w_3, \\\\dots, w_{n -1}$, where $w_k$ — the sum of the weights of the edges on the path between vertex $1$ and vertex $n$ in a $k$-perfect tree. If there is no $i$-long tree, then $w_i$ should be equal to $-1$.\n\nIn the first example, the $1$-perfect tree is defined by array $[ 1, 2, 1, 2 ]$ (i.e. $p_2 = 1$, $w_2 = 2$, $p_3 = 1$, $w_3 = 2$). The $2$-perfect tree is defined by array $[ 1, 2, 2, 1 ]$ (i.e $p_2 = 1$, $w_2 = 2$, $p_3 = 2$, $w_3 = 1$). Here are illustrations of the $1$-perfect tree and the $2$-perfect tree respectively (path from vertex $1$ to vertex $n$ is drawn with bold lines):\n\nIn the second example, there are no $k$-perfect trees, that can be obtained by permuting array $a$.\n\nIn the third example, only $4$-perfect tree and $5$-perfect tree can be obtained. These are defined by arrays $[ 1, 4, 2, 4, 3, 4, 4, 4, 4, 5 ]$ and $[ 1, 4, 2, 4, 3, 4, 4, 4, 5, 4 ]$ respectively. Here are illustrations of them:\n\n"},{"iden":"input","content":"The first line contains one integer $n$ ($2 <= n <= 10^5$) — the number of the vertices in the tree.The second line contains $2 dot.op n -2$ integers $a_1, a_2, \\\\dots, a_{2 n -2} (1 <= a_i <= n -1)$ — the elements of array $a$. "},{"iden":"output","content":"In one line, print $n -1$ space-separated integers $w_1, w_2, w_3, \\\\dots, w_{n -1}$, where $w_k$ — the sum of the weights of the edges on the path between vertex $1$ and vertex $n$ in a $k$-perfect tree. If there is no $i$-long tree, then $w_i$ should be equal to $-1$."},{"iden":"examples","content":"Input3\n1 1 2 2\nOutput2 3 Input3\n2 2 2 2\nOutput-1 -1 Input6\n1 4 5 4 4 4 3 4 4 2\nOutput-1 -1 -1 17 20 "},{"iden":"note","content":"In the first example, the $1$-perfect tree is defined by array $[ 1, 2, 1, 2 ]$ (i.e. $p_2 = 1$, $w_2 = 2$, $p_3 = 1$, $w_3 = 2$). The $2$-perfect tree is defined by array $[ 1, 2, 2, 1 ]$ (i.e $p_2 = 1$, $w_2 = 2$, $p_3 = 2$, $w_3 = 1$). Here are illustrations of the $1$-perfect tree and the $2$-perfect tree respectively (path from vertex $1$ to vertex $n$ is drawn with bold lines):  In the second example, there are no $k$-perfect trees, that can be obtained by permuting array $a$.In the third example, only $4$-perfect tree and $5$-perfect tree can be obtained. These are defined by arrays $[ 1, 4, 2, 4, 3, 4, 4, 4, 4, 5 ]$ and $[ 1, 4, 2, 4, 3, 4, 4, 4, 5, 4 ]$ respectively. Here are illustrations of them:   "}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the number of flagstones.  \nLet $ A = (a_1, a_2, \\dots, a_n) $ be a sequence of colors, where $ a_i \\in \\mathbb{Z}^+ $.  \nFor each color $ c $, let $ f(c) $ denote the frequency of $ c $ in $ A $.\n\n**Constraints**  \n1. $ 1 \\leq n \\leq 10^5 $  \n2. $ 1 \\leq a_i \\leq 10^5 $ for all $ i \\in \\{1, \\dots, n\\} $\n\n**Objective**  \nCompute the number of nonempty subsets of flagstones where all elements have the same color, modulo $ 10^9 + 7 $:  \n$$\n\\sum_{c \\in \\text{colors}} \\left(2^{f(c)} - 1\\right) \\mod (10^9 + 7)\n$$","simple_statement":"Count the number of nonempty subsets of flagstones where all flagstones in the subset have the same color. Print the result modulo $10^9 + 7$.","has_page_source":false}