{"problem":{"name":"Tri-Colored Paths","description":{"content":"You are given a simple connected undirected graph $G$ with $N$ vertices and $M$ edges. The vertices are numbered $1$ to $N$, and the $i$\\-th edge connects vertices $A_i$ and $B_i$. Find the number of ","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc153_f"},"statements":[{"statement_type":"Markdown","content":"You are given a simple connected undirected graph $G$ with $N$ vertices and $M$ edges. The vertices are numbered $1$ to $N$, and the $i$\\-th edge connects vertices $A_i$ and $B_i$.\nFind the number of ways to paint each edge of $G$ in color $1$, $2$, or $3$ so that the following condition is satisfied, modulo $998244353$.\n\n*   There is a simple path in $G$ that contains an edge in color $1$, an edge in color $2$, and an edge in color $3$.\n\nWhat is a simple path? A simple path is a pair of a sequence of vertices $(v_1, \\ldots, v_{k+1})$ and a sequence of edges $(e_1, \\ldots, e_k)$ that satisfies the following:\n\n*   $i\\neq j \\implies v_i\\neq v_j$;\n*   edge $e_i$ connects vertices $v_i$ and $v_{i+1}$.\n\n## Constraints\n\n*   $3 \\leq N\\leq 2\\times 10^5$\n*   $3 \\leq M\\leq 2\\times 10^5$\n*   $1 \\leq A_i, B_i \\leq N$\n*   The given graph is simple and connected.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$N$ $M$\n$A_1$ $B_1$\n$\\vdots$\n$A_M$ $B_M$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc153_f","tags":[],"sample_group":[["3 3\n1 2\n1 3\n3 2","0\n\nAny simple path in $G$ contains two or fewer edges, so there is no way to satisfy the condition."],["4 6\n1 2\n1 3\n1 4\n2 3\n2 4\n3 4","534"],["6 5\n1 3\n4 3\n5 4\n4 2\n1 6","144"],["6 7\n1 2\n2 3\n3 1\n4 5\n5 6\n6 4\n1 6","1794"]],"created_at":"2026-03-03 11:01:13"}}