Lưu ý: Đề bài đã được sửa đôi chút để đảm bảo bài có cách giải với độ phức tạp hợp lý.

Thành phố nơi An sống có ~N~ khu phố, được đánh số từ ~1~ đến ~N~ và được kết nối với nhau bởi ~M~ con đường hai chiều.

Nhà An ở khu phố ~1~. Một hành trình là một đường đi từ nhà đến các khu phố khác, sau đó quay lại về nhà của An sao cho không đi qua khu phố nào hai lần (trừ khu phố có nhà An).

Trong thành phố có ~(N-1)~ con đường quen thuộc với An. Để có thêm trải nghiệm mới, An chọn hành trình có đúng hai con đường không quen thuộc trong thành phố.

Yêu cầu: Hãy giúp An đếm số cách chọn hành trình có đúng hai con đường không quen thuộc trong thành phố.

Input

• Dòng đầu chứa hai số nguyên dương ~N, M~ (~N \le 2 \cdot 10^5, M \le 2 \cdot 10^5, N \le M~).

• ~(N-1)~ dòng tiếp theo, mỗi dòng chứa hai số nguyên dương ~u, v~ mô tả một con đường quen thuộc nối khu phố ~u~ với khu phố ~v~ (~u, v \le N, u \ne v~). Dữ liệu đảm bảo ~(N-1)~ cạnh này tạo thành một cây.

• ~(M-N+1)~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~u, v~ mô tả một con đường không quen thuộc nối khu phố ~u~ với khu phố ~v~.

Output

Ghi ra một số nguyên là số cách chọn hành trình có đúng hai con đường không quen thuộc trong thành phố.

Scoring

Sample Input 1

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

Sample Output 1

4