{"raw_statement":[{"iden":"problem statement","content":"We have a graph $G$ with $N$ vertices numbered $1$ through $N$ and $0$ edges. You are given sequences $u=(u_1,u_2,\\ldots,u_M),v=(v_1,v_2,\\ldots,v_M)$ of length $M$.\nYou will perform the following operation $(N-1)$ times.\n\n*   Choose $i$ $(1 \\leq i \\leq M)$ uniformly at random. Add to $G$ an undirected edge connecting Vertices $u_i$ and $v_i$.\n\nNote that the operation above will add a new edge connecting Vertices $u_i$ and $v_i$ even if $G$ already has one or more edges between them. In other words, the resulting $G$ may contain multiple edges.\nFor each $K=1,2,\\ldots,N-1$, find the probability, modulo $998244353$, that $G$ is a forest after the $K$\\-th operation.\nWhat is a forest?An undirected graph without a cycle is called a forest. A forest is not necessarily connected.\nDefinition of probability modulo $998244353$We can prove that the sought probability is always a rational number. Moreover, under the Constraints of this problem, it is guaranteed that, when the sought probability is represented by an irreducible fraction $\\frac{y}{x}$, $x$ is indivisible by $998244353$.\nThen, we can uniquely determine an integer $z$ between $0$ and $998244352$ (inclusive) such that $xz \\equiv y \\pmod{998244353}$. Print this $z$."},{"iden":"constraints","content":"*   $2 \\leq N \\leq 14$\n*   $N-1 \\leq M \\leq 500$\n*   $1 \\leq u_i,v_i \\leq N$\n*   $u_i\\neq v_i$\n*   All values in input are integers."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$ $M$\n$u_1$ $v_1$\n$\\vdots$\n$u_M$ $v_M$"},{"iden":"sample input 1","content":"3 2\n1 2\n2 3"},{"iden":"sample output 1","content":"1\n499122177\n\nLet us denote by $(u, v)$ the edge connecting Vertices $u$ and $v$.\nAfter the $1$\\-st operation, $G$ will have:\n\n*   Edge $(1, 2)$ with a probability of $1/2$;\n*   Edge $(2, 3)$ with a probability of $1/2$.\n\nIn both cases, $G$ is a forest, so the answer for $K=1$ is $1$.\nAfter the $2$\\-nd operation, $G$ will have:\n\n*   Edges $(1, 2)$ and $(1, 2)$ with a probability of $1/4$;\n*   Edges $(2, 3)$ and $(2, 3)$ with a probability of $1/4$;\n*   Edges $(1, 2)$ and $(2, 3)$ with a probability of $1/2$.\n\n$G$ is a forest only when $G$ has Edges $(1, 2)$ and $(2, 3)$. Therefore, the sought probability is $1/2$; when represented modulo $998244353$, it is $499122177$, which should be printed."},{"iden":"sample input 2","content":"4 5\n1 2\n1 2\n1 4\n2 3\n2 4"},{"iden":"sample output 2","content":"1\n758665709\n918384805"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}