{"raw_statement":[{"iden":"statement","content":"There are initially $N-1$ pairs of friends among FJ's $N$ cows labeled $1\\dots N$, forming a tree. The cows are\nleaving the farm for vacation one by one. On day $i$, the $i$ th cow leaves the\nfarm, and then all pairs of the $i$ th cow's friends still present on the farm\nbecome friends. \n\nFor each $i$ from $1$ to $N$, just before the $i$ th cow leaves,  how many\nordered triples of distinct cows $(a,b,c)$ are there such that none of $a,b,c$\nare on vacation, $a$ is friends with $b$, and $b$ is friends with $c$?"},{"iden":"input","content":"The first line contains $N$.\n\nThe next $N-1$ lines contain two integers $u_i$ and $v_i$ denoting that cows\n$u_i$ and $v_i$ are initially friends."},{"iden":"output","content":"The answers for $i$ from $1$ to $N$ on separate lines."},{"iden":"note","content":"For the first sample:  \n$(1,2,3)$ and $(3,2,1)$ are the triples just before cow $1$ leaves.  \nAfter cow\n$1$ leaves, there are less than $3$ cows left, so no triples are possible.\n\nFor the second sample:  \nAt the beginning, cow $1$ is friends with all other cows, and no other pairs of\ncows are friends, so the triples are $(a, 1, c)$ where $a, c$ are different cows\nfrom $\\{2, 3, 4\\}$, which gives $3 \\cdot 2 = 6$ triples.  \nAfter cow $1$ leaves, the remaining three cows are all friends, so the triples\nare just those three cows in any of the $3! = 6$ possible orders.  \nAfter cow $2$ leaves, there are less than $3$ cows left, so no triples are\npossible.  \n\n$2\\le N\\le 2\\cdot 10^5$, $1\\le u_i,v_i\\le N$.\n\n- Inputs 4-5: $N\\le 500$.\n- Inputs 6-10: $N\\le 5000$.\n- Inputs 11-20: No additional constraints.\n"}],"translated_statement":null,"sample_group":[["3\n1 2\n2 3\n","2\n0\n0\n"],["4\n1 2\n1 3\n1 4\n","6\n6\n0\n0\n"],["5\n3 5\n5 1\n1 4\n1 2\n","8\n10\n2\n0\n0\n"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}