평면 상에 3가지 종류의 점이 N개 있다. 각 점은 빨간색으로 칠해져 있거나, 파란색으로 칠해져 있거나, 아직 아무 색도 칠해져 있지 않을 수도 있다.

아직 색이 정해지지 않은 점들을 각각 빨간색 혹은 파란색으로 칠하고 싶다. 하지만 그냥 칠하는 것은 재미가 없기에, 다음 규칙을 추가하기로 했다.

"색을 모두 칠했을 때, 파란 점들로 만든 스패닝 트리와 빨간 점들로 만든 스패닝 트리가 겹치지 않는 방법이 적어도 하나 이상 있어야 한다."

이때 스패닝 트리를 이루는 간선들은 모두 어떤 점과 점 사이를 잇는 선분 모양이어야 한다.

위 규칙을 만족하면서 아직 색칠이 안된 정점에 색을 칠하는 경우의 수를 구하시오.

두 트리(평면ver) timer 1s memory 1024MB

두 트리(평면ver) 1s 1024MB