Tuyến Tập Luyện

Điểm: 1,00 (OI)

Giới hạn thời gian: 2.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

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 \leq N, M \leq 200 000$ )
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 \leq N, M \leq 200 000$
$1 \leq u, v \leq N$ , $u \neq v$
Đồ thị không có cạnh lặp

Ví dụ

Input	Output	Giải thích
5 8 1 2 1 3 1 4 1 5 2 3 3 4 4 5 5 2	4	Cây khung gồm các cạnh (1,2), (1,3), (1,4), (1,5). Bốn cặp tạo chu trình đơn là: (2-3, 3-4) qua cạnh 1-3; (2-3, 5-2) qua cạnh 1-2; (3-4, 4-5) qua cạnh 1-4; (4-5, 5-2) qua cạnh 1-5.

Bình luận

Không có bình luận tại thời điểm này.