It is difficult to exhaustively search all the \(3^N\) ways of painting within the execution time limit.
The basic idea is as follows.

• When the color of a vertex \(x\) has been determined, there are at most two candidate colors of a vertex connected to \(x\) with an edge, so if the graph is connected, we only have to search \(3 \times 2^{N - 1}\) ways of painting.
  

This time, the graph is not necessarily connected, but the overall number of ways of painting is equal to the product of the number of ways of painting of each connected component, so we can boil down to the case where the graph is connected if we process for each connected component.

There are various routes of implementation; the following is an example.

• Start a DFS (Depth-First Search) from an arbitrary vertex (here we use vertex \(1\)) without visiting the same vertex twice, and create an array \(s\) where the vertices are stored in the order of visi
• Since \(s_i (i \ge 2)\) is connected to at least one of \(s_1, s_2, s_3, \dots, s_{i - 1}\), so we can enumerate the ways of painting as follows:
  • Enumerate the three colors of \(s_1\)
  • Enumerate at most two colors of \(s_2\) (since there is at least one vertex \(s_i (i \lt 2)\) connected to \(s_2\), so there are at most two colors different to it)
  • Enumerate at most two colors of \(s_3\) (since there is at least one vertex \(s_i (i \lt 3)\) connected to \(s_3\), so there are at most two colors different to it)
  • \(\vdots\)

This algorithm works within a complexity like \(O(2^NN)\).