{"problem":{"name":"Random Isolation","description":{"content":"There is a tree with $N$ vertices numbered $1$ to $N$. The $i$\\-th edge connects vertices $A_i$ and $B_i$. Let us keep performing the following operation until each connected component of the graph ha","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc165_e"},"statements":[{"statement_type":"Markdown","content":"There is a tree with $N$ vertices numbered $1$ to $N$. The $i$\\-th edge connects vertices $A_i$ and $B_i$.\nLet us keep performing the following operation until each connected component of the graph has $K$ or fewer vertices.\n\n*   From the $N$ vertices, choose one uniformly at random that belongs to a connected component with $K+1$ or more vertices. Delete all edges with the chosen vertex as an endpoint.\n\nFind the expected value of the number of times the operation is performed, modulo $998244353$.\nHow to print an expected value modulo $\\text{mod }{998244353}$It can be proved that the sought expected value is always a rational number. Additionally, under the constraints of this problem, it can also be proved that when that value is represented as an irreducible fraction $\\frac{P}{Q}$, we have $Q \\not \\equiv 0 \\pmod{998244353}$. Thus, there is a unique integer $R$ such that $R \\times Q \\equiv P \\pmod{998244353}, 0 \\leq R < 998244353$. Report this $R$.\n\n## Constraints\n\n*   $1 \\leq K < N \\leq 100$\n*   $1 \\leq A_i,B_i \\leq N$\n*   The given graph is a tree.\n*   All input values are integers.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$N$ $K$\n$A_1$ $B_1$\n$A_2$ $B_2$\n$\\vdots$\n$A_{N-1}$ $B_{N-1}$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc165_e","tags":[],"sample_group":[["4 2\n1 2\n2 3\n2 4","249561090\n\nFor example, if the first operation chooses vertex $2$, it deletes all edges, after which each connected component has not more than two vertices, so we finish performing the operation. On the other hand, if the first operation chooses vertex $1$, there will still be a connected component with vertices $2$, $3$, and $4$, so we perform the second operation.\nThe expected value of the number of operations is $\\frac{7}{4}$."],["20 10\n16 8\n6 2\n18 3\n3 12\n5 1\n13 9\n13 19\n3 11\n5 13\n17 6\n8 14\n1 16\n16 20\n11 15\n3 10\n15 4\n5 18\n1 7\n1 17","181196154"]],"created_at":"2026-03-03 11:01:13"}}