{"problem":{"name":"Ex - K-Coloring","description":{"content":"You are given a simple undirected graph with $N$ vertices numbered $1$ to $N$ and $M$ edges numbered $1$ to $M$. Edge $i$ connects vertex $u_i$ and vertex $v_i$. Find the number, modulo $998244353$, o","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":8000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc294_h"},"statements":[{"statement_type":"Markdown","content":"You are given a simple undirected graph with $N$ vertices numbered $1$ to $N$ and $M$ edges numbered $1$ to $M$. Edge $i$ connects vertex $u_i$ and vertex $v_i$.\nFind the number, modulo $998244353$, of ways to write an integer between $1$ and $K$, inclusive, on each vertex of this graph to satisfy the following condition:\n\n*   two vertices connected by an edge always have different numbers written on them.\n\n## Constraints\n\n*   $1 \\leq N \\leq 30$\n*   $0 \\leq M \\leq \\min \\left(30, \\frac{N(N-1)}{2} \\right)$\n*   $1 \\leq K \\leq 10^9$\n*   $1 \\leq u_i \\lt v_i \\leq N$\n*   The given graph is simple.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$N$ $M$ $K$\n$u_1$ $v_1$\n$u_2$ $v_2$\n$\\vdots$\n$u_M$ $v_M$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc294_h","tags":[],"sample_group":[["4 3 2\n1 2\n2 4\n2 3","2\n\nHere are the two ways to satisfy the condition.\n\n*   Write $1$ on vertices $1, 3, 4$, and write $2$ on vertex $2$.\n*   Write $1$ on vertex $2$, and write $2$ on vertex $1, 3, 4$."],["4 0 10","10000\n\nAll $10^4$ ways satisfy the condition."],["5 10 5\n3 5\n1 3\n1 2\n1 4\n3 4\n2 5\n4 5\n1 5\n2 3\n2 4","120"],["5 6 294\n1 2\n2 4\n1 3\n2 3\n4 5\n3 5","838338733"],["7 12 1000000000\n4 5\n2 7\n3 4\n6 7\n3 5\n5 6\n5 7\n1 3\n4 7\n1 5\n2 3\n3 6","418104233"]],"created_at":"2026-03-03 11:01:14"}}