{"problem":{"name":"Red and Blue Graph","description":{"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$. There are ","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc262_e"},"statements":[{"statement_type":"Markdown","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.\n\n## Constraints\n\n*   $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.\n\n## Input\n\nInput 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$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc262_e","tags":[],"sample_group":[["4 4 2\n1 2\n1 3\n2 3\n3 4","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."],["10 10 3\n1 2\n2 4\n1 5\n3 6\n3 9\n4 10\n7 8\n9 10\n5 9\n3 4","64"]],"created_at":"2026-03-03 11:01:14"}}