{"raw_statement":[{"iden":"problem statement","content":"You are given a tree with $N$ vertices. The vertices are numbered $1$ through $N$, and the $i$\\-th edge connects vertex $a_i$ and vertex $b_i$.\nSolve the following problem for each $x=1,2,\\ldots,N$:\n\n*   There are $(2^N-1)$ non-empty subsets $V$ of the tree's vertices. Find the number, modulo $998244353$, of such $V$ that the subgraph induced by $V$ has exactly $x$ connected components.\n\nWhat is an induced subgraph? Let $S$ be the subset of the vertices of a graph $G$; then the subgraph of $G$ induced by $S$ is a graph whose vertex set is $S$ and whose edge set consists of all edges of $G$ whose both ends are contained in $S$."},{"iden":"constraints","content":"*   $1 \\leq N \\leq 5000$\n*   $1 \\leq a_i \\lt b_i \\leq N$\n*   The given graph is a tree."},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$N$\n$a_1$ $b_1$\n$\\vdots$\n$a_{N-1}$ $b_{N-1}$"},{"iden":"sample input 1","content":"4\n1 2\n2 3\n3 4"},{"iden":"sample output 1","content":"10\n5\n0\n0\n\nThe induced subgraph will have two connected components in the following five cases and one in the others.\n\n*   $V = {1,2,4}$\n*   $V = {1,3}$\n*   $V = {1,3,4}$\n*   $V = {1,4}$\n*   $V = {2,4}$"},{"iden":"sample input 2","content":"2\n1 2"},{"iden":"sample output 2","content":"3\n0"},{"iden":"sample input 3","content":"10\n3 4\n3 6\n6 9\n1 3\n2 4\n5 6\n6 10\n1 8\n5 7"},{"iden":"sample output 3","content":"140\n281\n352\n195\n52\n3\n0\n0\n0\n0"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}