\(3^N\) 通りの塗り方を全部探索する方法では実行時間制限に間に合わせるのは困難です。
基本的なアイディアは以下の通りです。

• ある頂点 \(x\) の色を決めた時、\(x\) と辺で繋がっている頂点の色の探索候補は \(2\) 通りしかないから、グラフが連結なら \(3 \times 2^{N - 1}\) 通りの塗り方だけ探索すればよい。
  

今回グラフは連結とは限りませんが、連結成分ごとの塗り方の数の積が全体の塗り方の数となるので連結成分ごとに処理すればグラフが連結な場合に帰着することができます。

実装方針は色々ありますが、以下が \(1\) 例です。

• 適当な頂点 (ここでは頂点 \(1\) とする) から同じ頂点を \(2\) 度通らないDFS (深さ優先探索) をし、頂点を訪れた順に入れた配列 \(s\) を作る
• \(s_i (i \ge 2)\) は \(s_1, s_2, s_3, \dots, s_{i - 1}\) のいずれかと隣接しているので、以下のように塗り方を探索できる
  
  • \(s_1\) の色を \(3\) 通り探索する
  • \(s_2\) の色を高々 \(2\) 通り探索する (\(s_2\) が隣接している頂点 \(s_i (i \lt 2)\) が少なくとも \(1\) つあるはずなので、それらと違う色は高々 \(2\) つ)
  • \(s_3\) の色を高々 \(2\) 通り探索する (\(s_3\) が隣接している頂点 \(s_i (i \lt 3)\) が少なくとも \(1\) つあるはずなので、それらと違う色は高々 \(2\) つ)
  • \(\vdots\)

このアルゴリズムは \(O(2^NN)\) などの計算量で動作します。