어떤 도시에는 \(N\) 개의 명소가 \(1\) 번부터 \(N\) 번까지 번호가 붙어 있고, 일부 명소 쌍 사이에 양방향 도로가 놓여 있습니다.

관광객은 항상 \(1\) 번 명소에서 출발하여, 모든 명소를 정확히 한 번씩 방문하는 코스를 짜려고 합니다. 도로가 있는 명소끼리만 곧바로 이동할 수 있습니다.

조건을 만족하는 서로 다른 코스(방문 순서)의 개수를 구하세요. 방문하는 순서가 다르면 다른 코스로 봅니다.

\(1 \le N \le 15\)

첫 줄에 명소 수 \(N\) 과 도로 수 \(M\) 이 주어집니다. (\(1 \le N \le 15\), \(0 \le M \le \frac{N(N-1)}{2}\))

이어 \(M\) 개의 줄에 도로로 연결된 두 명소 번호 \(a\), \(b\) 가 주어집니다. 같은 도로가 중복으로 주어지지 않으며 \(a \ne b\) 입니다.

\(1\) 번에서 출발해 모든 명소를 한 번씩 방문하는 코스의 수를 출력합니다.

riseoj 작성

출처 Original