Cô bò Bessie nhận ra rằng mình cần tập thể dục nhiều hơn để giữ vóc dáng cân đối. Cô cần bạn giúp chọn các lộ trình tiềm năng quanh trang trại cho việc chạy bộ buổi sáng.

Trang trại gồm \(N\) cánh đồng (\(1 \leq N \leq 2 \cdot 10^5\)), được đánh số thuận tiện từ \(1 \ldots N\), và được nối với nhau một cách thuận tiện bởi một tập gồm \(M\) đường mòn hai chiều (\(1 \leq M \leq 2 \cdot 10^5\)). Vì là những sinh vật có thói quen, các cô bò thường chỉ sử dụng một tập con gồm \(N-1\) đường mòn nhất định cho mọi hoạt động di chuyển hằng ngày giữa các cánh đồng — chúng gọi đây là các đường mòn "tiêu chuẩn". Chỉ sử dụng các đường mòn tiêu chuẩn, ta vẫn có thể đi từ bất kỳ cánh đồng nào đến bất kỳ cánh đồng nào khác.

Để buổi chạy bộ sáng thú vị hơn, Bessie quyết định chọn một lộ trình có sử dụng một số đường mòn không tiêu chuẩn. Tuy nhiên, cô đã quá quen với các đường mòn tiêu chuẩn nên không muốn dùng quá nhiều đường mòn không tiêu chuẩn trên lộ trình. Sau khi suy nghĩ, cô quyết định một lộ trình tốt là một chu trình đơn (quay lại điểm xuất phát và không đi qua cánh đồng nào quá một lần) chứa đúng hai đường mòn không tiêu chuẩn.

Hãy giúp Bessie đếm số lộ trình tốt mà cô có thể sử dụng. Hai lộ trình được xem là giống nhau nếu chúng gồm cùng một tập đường mòn.

Dữ liệu vào

Dòng đầu tiên chứa \(N\) và \(M\). Mỗi dòng trong \(M\) dòng tiếp theo chứa hai số nguyên \(a_i\) và \(b_i\), mô tả hai đầu mút của một đường mòn. \(N-1\) đường mòn đầu tiên là các đường mòn tiêu chuẩn.

Dữ liệu ra

In ra tổng số lộ trình mà Bessie có thể muốn sử dụng.

Ví dụ

5 8
1 2
1 3
1 4
1 5
2 3
3 4
4 5
5 2

4

Nguồn

Đề bài gốc: USACO 2019 January Contest, Platinum — Exercise Route

Tác giả: Dhruv Rohatgi