Vi mô và Hoán vị

Trong một buổi làm việc tại nhà sách, FullHouse Dev được giao một bài toán thú vị về lý thuyết đồ thị. Họ cần giúp nhà sách sắp xếp các kệ sách theo một cách đặc biệt, được mô phỏng thành bài toán về đồ thị và hoán vị.

Bài toán

FullHouse Dev có một đồ thị với \(N\) đỉnh được đánh số từ 1 đến \(N\) và \(M\) cạnh hai chiều. Họ cần tìm số lượng hoán vị may mắn trong đồ thị. Một hoán vị của các đỉnh được gọi là may mắn nếu với mọi đỉnh \(i\), trong đó \(1 \leq i < N\), tồn tại một cạnh nối giữa đỉnh thứ \(i\) và đỉnh thứ \(i+1\) trong hoán vị đó.

INPUT FORMAT:

• Dòng đầu tiên chứa hai số nguyên \(N\) và \(M\) cách nhau bởi dấu cách.
• \(M\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(X\) và \(Y\) cho biết có cạnh nối giữa đỉnh \(X\) và đỉnh \(Y\).

OUTPUT FORMAT:

• In ra số lượng hoán vị may mắn trong đồ thị.

Ràng buộc:

• \(1 \leq N \leq 8\)
• \(0 \leq M \leq N×(N-1)/2\)
• \(1 \leq X, Y \leq N\)

Ví dụ

INPUT

3 2
1 2
2 3

OUTPUT

2

Giải thích

Có hai hoán vị may mắn có thể xảy ra:

• 1-2-3: hợp lệ vì có cạnh nối 1-2 và 2-3
• 3-2-1: hợp lệ vì có cạnh nối 3-2 và 2-1