Hành trình kỳ lạ

Cho một đồ thị vô hướng gồm $n$ đỉnh và $m$ cạnh. Đồ thị có thể chứa khuyên (cạnh nối một đỉnh với chính nó), nhưng không có hai cạnh nào nối cùng một cặp đỉnh. Nói riêng, mỗi đỉnh có nhiều nhất một khuyên.

Một hành trình là một dãy các cạnh đi liên tiếp nhau, có thể bắt đầu và kết thúc tại đỉnh bất kỳ. Hành trình được gọi là tốt nếu nó đi qua $m-2$ cạnh đúng hai lần và $2$ cạnh còn lại đúng một lần. Như vậy mọi cạnh của đồ thị đều phải được đi qua.

Hai hành trình tốt được coi là khác nhau nếu tập hai cạnh mà chúng chỉ đi qua một lần là khác nhau.

Hãy đếm số hành trình tốt.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $m$: số đỉnh và số cạnh.
• $m$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u$ và $v$, mô tả một cạnh nối đỉnh $u$ và đỉnh $v$.

Dữ liệu ra

Một số nguyên duy nhất là số hành trình tốt.

Ràng buộc

• $1\le n,m\le {10}^6$
• $1\le u,v\le n$
• Không có cặp đỉnh nào được nối bởi hai cạnh khác nhau.

Ví dụ