Vitaly và chu trình lẻ

Cho một đồ thị vô hướng gồm $n$ đỉnh và $m$ cạnh, không có khuyên (cạnh nối một đỉnh với chính nó) và không có cạnh song song. Đồ thị không nhất thiết liên thông.

Hãy tìm hai giá trị:

• $t$ — số cạnh ít nhất cần thêm vào đồ thị để tạo ra một chu trình đơn có độ dài lẻ với nhiều hơn một đỉnh (mỗi đỉnh xuất hiện không quá một lần trong chu trình).
• $w$ — số cách thêm đúng $t$ cạnh để đạt được mục tiêu trên.

Các cạnh thêm vào không được tạo thành khuyên hoặc cạnh song song với cạnh đã có. Hai cách thêm cạnh được coi là giống nhau nếu tập hợp các cạnh được thêm là như nhau.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $m$.
• $m$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $a_i,b_i$ ($1\le a_i,b_i\le n$, $a_i\ne b_i$) — mô tả một cạnh.

Đồ thị đảm bảo không có khuyên và không có cạnh song song.

Dữ liệu ra

In ra hai số nguyên $t$ và $w$ cách nhau bởi một dấu cách.

Ràng buộc

• $3\le n\le {10}^5$
• $0\le m\le {10}^5$

Ví dụ