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

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

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

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

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

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

이 때, 주어진 지도를 위 조건을 만족하면서 5가지 색으로 색칠할 수 있는 모든 경우의 수를 반환하는 프로그램을 작성하세요. (뜬금없죠? ..근데 딱히 연관지을 게 없어서..)

입력

• 첫 번째 줄에 지도 위에 그려진 국가의 수 N, 지도에서 국경이 인접한 국가들의 수 M이 공백을 사이로 두고 주어집니다.
• 두 번째 줄부터 M + 1번째 줄까지 인접한 두 국가의 번호가 공백을 사이로 두고 주어집니다. 국가들의 번호는 1 이상 N 이하의 자연수입니다. 만약 M = 0이면 첫 번째 줄만 입력받으면 됩니다.

출력

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

제약 조건

• 1 ≤ N ≤ 20
• 0 ≤ M ≤ N(N-1)/2

입출력 예

입력

2 1
1 2

출력

12

입력

4 3
1 2
2 3
3 1

출력

96

출처: GENIUSainta.com