{"problem":{"name":"RGB Coloring 2","description":{"content":"We have a simple undirected graph with $N$ vertices and $M$ edges. The vertices are numbered $1$ through $N$, and the edges are numbered $1$ through $M$.   Edge $i$ connects Vertex $A_i$ and Vertex $B","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc199_d"},"statements":[{"statement_type":"Markdown","content":"We have a simple undirected graph with $N$ vertices and $M$ edges. The vertices are numbered $1$ through $N$, and the edges are numbered $1$ through $M$.  \nEdge $i$ connects Vertex $A_i$ and Vertex $B_i$.  \nFind the number of ways to paint each vertex in this graph red, green, or blue so that the following condition is satisfied:\n\n*   two vertices directly connected by an edge are always painted in different colors.\n\nHere, it is not mandatory to use all the colors.\n\n## Constraints\n\n*   $1 \\le N \\le 20$\n*   $0 \\le M \\le \\frac{N(N - 1)}{2}$\n*   $1 \\le A_i \\le N$\n*   $1 \\le B_i \\le N$\n*   The given graph is simple (that is, has no multi-edges and no self-loops).\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$ $M$\n$A_1$ $B_1$\n$A_2$ $B_2$\n$A_3$ $B_3$\n$\\hspace{15pt} \\vdots$\n$A_M$ $B_M$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc199_d","tags":[],"sample_group":[["3 3\n1 2\n2 3\n3 1","6\n\nLet $c_1, c_2, c_3$ be the colors of Vertices $1, 2, 3$ and `R`, `G`, `B` denote red, green, blue, respectively. There are six ways to satisfy the condition:\n\n*   $c_1c_2c_3 = $ `RGB`\n*   $c_1c_2c_3 = $ `RBG`\n*   $c_1c_2c_3 = $ `GRB`\n*   $c_1c_2c_3 = $ `GBR`\n*   $c_1c_2c_3 = $ `BRG`\n*   $c_1c_2c_3 = $ `BGR`"],["3 0","27\n\nSince the graph has no edge, we can freely choose the colors of the vertices."],["4 6\n1 2\n2 3\n3 4\n2 4\n1 3\n1 4","0\n\nThere may be no way to satisfy the condition."],["20 0","3486784401\n\nThe answer may not fit into the $32$\\-bit signed integer type."]],"created_at":"2026-03-03 11:01:13"}}