{"trustable":true,"sections":[{"title":"","value":{"format":"MD","content":"\u003ch3\u003eRead problems statements in \u003ca target\u003d\"_blank\" \nhref\u003d\"https://www.codechef.com/download/translated/MARCH18/mandarin/CUTTREE.pdf\"\u003eMandarin chinese\u003c/a\u003e, \u003ca target\u003d\"_blank\" \nhref\u003d\"https://www.codechef.com/download/translated/MARCH18/russian/CUTTREE.pdf\"\u003eRussian\u003c/a\u003e and \u003ca target\u003d\"_blank\" \nhref\u003d\"https://www.codechef.com/download/translated/MARCH18/vietnamese/CUTTREE.pdf\"\u003eVietnamese\u003c/a\u003e as well.\u003c/h3\u003e\n\n\u003cp\u003e\nA forest is an undirected acyclic graph. Let us define the \u003ci\u003estrength\u003c/i\u003e of a forest as the sum of squares of sizes of its connected components. (Clearly, a tree with \u003cb\u003en\u003c/b\u003e nodes has strength \u003cb\u003en\u003csup\u003e2\u003c/sup\u003e\u003c/b\u003e.)\u003c/p\u003e \n\n\u003cp\u003e\nChef has found a tree with \u003cb\u003eN\u003c/b\u003e nodes on day 0. On each of the next \u003cb\u003eN-1\u003c/b\u003e days, he\u0027s going to remove one edge. Let\u0027s denote the forest that remains after \u003cb\u003ei\u003c/b\u003e days by \u003cb\u003eF\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e, for each 1 ≤ \u003cb\u003ei\u003c/b\u003e ≤ \u003cb\u003eN-1\u003c/b\u003e; also, let\u0027s denote the original tree by \u003cb\u003eF\u003csub\u003e0\u003c/sub\u003e\u003c/b\u003e. On day \u003cb\u003ei\u003c/b\u003e, \u003cb\u003eF\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e is created by randomly uniformly choosing one edge from \u003cb\u003eF\u003csub\u003ei-1\u003c/sub\u003e\u003c/b\u003e and removing it.\n\u003c/p\u003e\n\n\u003cp\u003e\nLet \u003cb\u003eE\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e be the expected value of strength of the forest \u003cb\u003eF\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e, for each 0 ≤ \u003cb\u003ei\u003c/b\u003e ≤ \u003cb\u003eN-1\u003c/b\u003e. It can be proven that this number can be written in the form \u003cb\u003eP\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e / \u003cb\u003eQ\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e, where \u003cb\u003egcd\u003c/b\u003e(\u003cb\u003eP\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e, \u003cb\u003eQ\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e)\u003c/b\u003e \u003d 1 and \u003cb\u003egcd\u003c/b\u003e(\u003cb\u003eQ\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e, 10\u003csup\u003e9\u003c/sup\u003e + 7) \u003d 1. Let \u003cb\u003eR\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e \u003d \u003cb\u003eP\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e · \u003cb\u003eQ\u003csub\u003ei\u003c/sub\u003e\u003csup\u003e-1\u003c/sup\u003e\u003c/b\u003e mod 10\u003csup\u003e9\u003c/sup\u003e + 7, where \u003cb\u003eQ\u003csub\u003ei\u003c/sub\u003e\u003csup\u003e-1\u003c/sup\u003e\u003c/b\u003e denotes the modular inverse of \u003cb\u003eQ\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e modulo 10\u003csup\u003e9\u003c/sup\u003e + 7.\n\u003c/p\u003e\n\n\u003cp\u003e\nFind the values of \u003cb\u003eR\u003csub\u003e0\u003c/sub\u003e, R\u003csub\u003e1\u003c/sub\u003e, ..., R\u003csub\u003eN-1\u003c/sub\u003e\u003c/b\u003e.\n\u003c/p\u003e\n\n\u003ch3\u003eInput\u003c/h3\u003e\n\u003cul\u003e\n\u003cli\u003eThe first line of the input contains a single integer \u003cb\u003eN\u003c/b\u003e — the number of nodes in the tree.\u003c/li\u003e\n\u003cli\u003e\u003cb\u003eN-1\u003c/b\u003e lines follow. Each of these lines contains two space-separated integers \u003cb\u003eu\u003c/b\u003e and \u003cb\u003ev\u003c/b\u003e denoting an edge between nodes \u003cb\u003eu\u003c/b\u003e and \u003cb\u003ev\u003c/b\u003e in the tree.\u003c/li\u003e\n\u003c/ul\u003e\n\n\u003ch3\u003eOutput\u003c/h3\u003e\n\u003cp\u003e\nPrint a single line containing \u003cb\u003eN\u003c/b\u003e space-separated integers \u003cb\u003eR\u003csub\u003e0\u003c/sub\u003e, R\u003csub\u003e1\u003c/sub\u003e, ..., R\u003csub\u003eN-1\u003c/sub\u003e\u003c/b\u003e.\n\u003c/p\u003e\n\n\u003ch3\u003eConstraints\u003c/h3\u003e\n\u003cul\u003e\n\u003cli\u003e 1 ≤ \u003cb\u003eN\u003c/b\u003e ≤ 10\u003csup\u003e5\u003csup\u003e \u003c/li\u003e\n\u003cli\u003e 1 ≤ \u003cb\u003eu\u003c/b\u003e, \u003cb\u003ev\u003c/b\u003e ≤ \u003cb\u003eN\u003c/b\u003e \u003c/li\u003e\n\u003c/ul\u003e\n\n\u003ch3\u003eSubtasks\u003c/h3\u003e\n\u003cp\u003e\u003cb\u003eSubtask #1 (25 points):\u003c/b\u003e 1 ≤ \u003cb\u003eN\u003c/b\u003e ≤ 10\u003csup\u003e3\u003c/sup\u003e\u003c/p\u003e\n\n\u003cp\u003e\u003cb\u003eSubtask #2 (75 points):\u003c/b\u003e original constraints\u003c/p\u003e"}},{"title":"Sample 1","value":{"format":"MD","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e5\n1 2\n1 3\n2 4\n2 5\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e25 16 333333346 7 5\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}