Tuyến Tập Luyện

Farmer John có $N$ cánh đồng và $M$ con đường mòn. $N-1$ con đường mòn đầu tiên tạo thành một cây khung nối tất cả các cánh đồng (gọi là đường mòn tiêu chuẩn). Các con đường mòn còn lại (từ thứ $N$ đến thứ $M$) được gọi là đường mòn phi tiêu chuẩn.

Bessie muốn tập luyện bằng cách chọn đúng hai đường mòn phi tiêu chuẩn sao cho hai đường mòn đó cùng với các cạnh cây khung tạo thành một chu trình đơn (mỗi cánh đồng xuất hiện đúng một lần trong chu trình).

Hãy đếm số cặp đường mòn phi tiêu chuẩn thỏa mãn điều kiện trên.

Dữ liệu vào

• Dòng đầu: hai số nguyên $N$ và $M$ ($1\le N,M\le 200000$)
• $M$ dòng tiếp theo, mỗi dòng gồm hai số nguyên $u$ và $v$ mô tả một con đường mòn nối cánh đồng $u$ và $v$
  • $N-1$ dòng đầu là các đường mòn tiêu chuẩn (cây khung)
  • $M-N+1$ dòng sau là các đường mòn phi tiêu chuẩn

Dữ liệu ra

Một số nguyên: số cặp đường mòn phi tiêu chuẩn thỏa mãn.

Ràng buộc

• $1\le N,M\le 200000$
• $1\le u,v\le N$, $u\ne v$
• Đồ thị không có cạnh lặp

Ví dụ