편의점의 이웃 진열

문제

작은 편의점에서 계산대 옆의 일렬 진열대를 새로 꾸미려고 한다. 진열할 상품은 N개이며, 상품에는 1번부터 N번까지 서로 다른 번호가 붙어 있다. 진열대에는 왼쪽부터 오른쪽까지 N개의 자리가 있고, 모든 상품을 정확히 하나씩 놓아야 한다. 상품의 번호는 상품을 구별하기 위한 것이며, 번호가 연속한다고 해서 서로 비슷한 상품이라는 뜻은 아니다. 점장은 일부 상품 쌍을 바로 이웃하여 놓지 않기로 했다. 이런 쌍은 포장의 돌출된 부분이 서로 걸리거나 진열 안내판을 함께 가릴 수 있는 조합이다. 금지된 쌍에 속한 두 상품 사이에는 다른 상품이 적어도 하나 있어야 한다. 두 상품 중 어느 것이 왼쪽에 있는지는 관계없다. 따라서 상품 u와 상품 v가 금지된 쌍이면 u 바로 오른쪽에 v를 놓는 것과 v 바로 오른쪽에 u를 놓는 것이 모두 금지된다. 진열대는 일렬이므로 가장 왼쪽 자리와 가장 오른쪽 자리는 서로 이웃하지 않는다. 금지된 쌍에 포함되어 있더라도 양 끝에 놓은 두 상품 사이에는 별도의 이웃 제한을 적용하지 않는다. 입력으로 주어지지 않은 상품 쌍은 자유롭게 이웃하여 놓을 수 있으며, 각 상품을 놓을 수 있는 자리에 대한 다른 제한은 없다. 점장은 조건을 지키는 진열 순서가 모두 몇 개인지 알고 싶어 한다. 왼쪽부터 읽은 상품 번호의 나열이 한 자리라도 다르면 서로 다른 진열 순서로 센다. 따라서 어떤 순서를 좌우로 뒤집어 얻은 순서도 번호의 나열이 달라지면 별개의 순서다. 상품이 하나뿐이면 그 상품만 놓는 한 가지 순서가 가능하다. 조건을 만족하는 순서가 하나도 없을 때는 가능한 순서의 수가 0이다. 주어진 모든 이웃 금지 조건을 만족하는 진열 순서의 수를 구하는 프로그램을 작성한다.

입력

첫째 줄에 정수 N과 M이 주어진다. 1 ≤ N ≤ 9이고, 0 ≤ M ≤ N(N-1)/2이다.
다음 M개 줄에는 이웃하여 놓을 수 없는 상품 번호 u와 v가 주어진다. 1 ≤ u < v ≤ N이다. 같은 쌍은 두 번 이상 주어지지 않는다.

출력

조건을 만족하는 진열 순서의 수를 정수 하나로 출력한다. 가능한 순서가 없으면 0을 출력한다.

3 1
1 2

2

1 0

1

3 3
1 2
1 3
2 3

0

출처: Devin.KR 자체 제작