Informatica Online Judge

  지도 색칠하기 [0758 / 02F6]

Time Limit(Test case) : 3000(ms)
Number of users who solved : 8   Total Tried : 18


The Champion of this Problem (C++) : chan4928 - 0ms / 2492byte
My Best Submission (C++) : N/A

[]

Background

4색 정리가 증명되었지만 사실 지도와 4색 정리는 큰 연관이 없고, 대부분의 지도 제작자들은 지도를 제작할 때 색을 최소한으로 사용하려는 노력을 크게 하지 않는다고 합니다.

이에 승현이는 고정관념을 깨트리기 위해 4가지의 색으로 지도를 색칠하기로 하고, 아래의 4가지 색을 선택했습니다. 단, 지도를 색칠할 때 인접한 국가들끼리는 다른 색을 칠해야 하고, 같은 국가에는 같은 색을 칠해야 합니다.



그런데 생각해 보니, 강과 바다는 무조건 파란색으로 칠해야 했고, 그래서 4가지 색으로 지도를 색칠하기에는 역부족이었습니다.

좋은 방법이 없을까 생각하던 승현이는 결국 노랑, 연두, 초록, 파랑, 주황의 5가지 색으로 지도를 색칠하기로 했습니다. 강과 바다는 파란색으로 칠해야 하므로, 육지를 칠하는 데 사용할 수 있는 색은 파란색을 제외한 4개뿐입니다.



문제는, [그림 1]과 같이 한 나라가 여러 동강이 나 있을 수도 있다는 것입니다. (식민지를 건설한다거나, 땅을 사고판다거나, ..)



이런 경우, 위에 명시된 대로 같은 국가에 같은 색, 위 그림에서는 2번 국가에 같은 색을 칠해야 합니다. 따라서 [그림 2]와 같이 지도를 색칠할 수 없습니다.



주어진 지도를 위 조건을 만족하면서 5가지 색으로 색칠할 수 있는 모든 경우의 수를 구하는 프로그램을 작성하세요.

Input

첫째 줄에 N과 M이 공백을 사이로 두고 주어집니다.
둘째 줄부터 M+1번째 줄까지: (i+2)번째 줄에 A[i]와 B[i]가 공백을 사이로 두고 주어집니다.
(단, 1 ≤ N ≤ 20, 0 ≤ M ≤ N(N-1)/2 )

Output

주어진 지도를 색칠할 수 있는 모든 경우의 수를 출력합니다.

IO Example

입력
2 1
1 2

출력
12

*설명 : 1번 예제는 아래 그림을 표현한 것입니다. 색칠할 수 있는 경우의 수는 4×3=12가지입니다.



입력2
4 3
1 2
2 3
3 1

출력2
96

* 설명 : 2번 예제는 아래 그림을 표현한 것입니다. 색칠할 수 있는 경우의 수는 4×3×2×4=96가지입니다.



출처: GENIUSainta.com

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]