{"raw_statement":[{"iden":"problem statement","content":"You are given a simple undirected graph with $N$ vertices and $M$ edges. The vertices are numbered $1, \\dots, N$, and the $i$\\-th $(1 \\leq i \\leq M)$ edge connects Vertices $U_i$ and $V_i$.\nThere are $2^N$ ways to paint each vertex red or blue. Find the number, modulo $998244353$, of such ways that satisfy all of the following conditions:\n\n*   There are exactly $K$ vertices painted red.\n*   There is an even number of edges connecting vertices painted in different colors."},{"iden":"constraints","content":"*   $2 \\leq N \\leq 2 \\times 10^5$\n*   $1 \\leq M \\leq 2 \\times 10^5$\n*   $0 \\leq K \\leq N$\n*   $1 \\leq U_i \\lt V_i \\leq N \\, (1 \\leq i \\leq M)$\n*   $(U_i, V_i) \\neq (U_j, V_j) \\, (i \\neq j)$\n*   All values in input are integers."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$ $M$ $K$\n$U_1$ $V_1$\n$\\vdots$\n$U_M$ $V_M$"},{"iden":"sample input 1","content":"4 4 2\n1 2\n1 3\n2 3\n3 4"},{"iden":"sample output 1","content":"2\n\nThe following two ways satisfy the conditions.\n\n*   Paint Vertices $1$ and $2$ red and Vertices $3$ and $4$ blue.\n*   Paint Vertices $3$ and $4$ red and Vertices $1$ and $2$ blue.\n\nIn either of the ways above, the $2$\\-nd and $3$\\-rd edges connect vertices painted in different colors."},{"iden":"sample input 2","content":"10 10 3\n1 2\n2 4\n1 5\n3 6\n3 9\n4 10\n7 8\n9 10\n5 9\n3 4"},{"iden":"sample output 2","content":"64"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}