Cho đồ thị vô hướng không trọng số gồm ~N~ đỉnh đánh số từ ~1~ đến ~N~ và ~M~ cạnh. Đồ thị không có khuyên và không có hai cạnh trùng nhau.

Hãy đếm số đường đi bắt đầu tại đỉnh ~1~ và đi qua mọi đỉnh đúng một lần. Hai đường đi khác nhau nếu dãy thứ tự các đỉnh được thăm khác nhau.

Input

• Dòng đầu gồm hai số nguyên ~N~ và ~M~, lần lượt là số đỉnh và số cạnh.
• Trong ~M~ dòng tiếp theo, dòng thứ ~i~ gồm hai số nguyên ~a_i~ và ~b_i~, biểu diễn một cạnh nối hai đỉnh đó.

Output

• In một số nguyên là số đường đi thỏa mãn.

Giới hạn

• ~2 ≤ N ≤ 8~.
• ~0 ≤ M ≤ N(N - 1) / 2~.
• ~1 ≤ a_i < b_i ≤ N~ với mọi ~1 ≤ i ≤ M~.
• Không có khuyên và cạnh trùng.

Ví dụ

Input

3 3
1 2
1 3
2 3

Output

2

Giải thích ví dụ

Có đúng hai thứ tự thăm hợp lệ là 1 → 2 → 3 và 1 → 3 → 2. Cả hai đều bắt đầu tại đỉnh 1, sử dụng các cạnh có trong đồ thị và đi qua mỗi đỉnh đúng một lần, nên kết quả là 2.