Nam đang tìm hiểu cách các máy tính trong 1 mạng được kết nối với nhau. Mạng máy tính có N máy tính được kết nối bởi N - 1 dây cáp mạng. Các máy tính được đánh số từ 1 đến N và mỗi dây cáp mạng nối hai máy tính khác nhau.

Nam muốn tìm hành trình tối ưu có độ dài chính xác là 2 nếu một gói dữ liệu được gửi từ máy u đến máy v. Đường đi ngắn nhất giữa u và v phải đi qua đúng một máy trung gian (tức là đường đi hành trình có độ dài chính xác là 2).

Mô tả chi tiết: Một hành trình dài K từ máy S đến máy T là một dãy thứ tự các máy: V_0 → V_1 → V_2 → ⋯ → V_k. Trong đó:

• V_0=S
• V_k =T
• Với mọi chỉ số hợp lệ i, $Vi và V{i+1}$ được kết nối trực tiếp bằng một dây cáp.

Một hành trình được gọi là tối ưu nếu:

• Không có hành trình nào ngắn hơn với cùng điểm bắt đầu và kết thúc.
• Hai hành trình: V_0 → V_1 → V_2 → ⋯ → V_k và W_0 → W_1→ W_2 → ⋯ → W_l được xem là khác nhau nếu k≠ℓ hoặc tồn tại ít nhất một chỉ số j sao cho V_i≠ W_j

Yêu cầu bài toán: Nam cần xác định có bao nhiêu các cặp máy tính có thể được nối với nhau bằng một hành trình tối ưu có độ dài chính xác là 2.

• Dòng đầu tiên chứa số nguyên N chứa số lượng máy tính
• N−1 dòng tiếp theo: mỗi dòng chứa 2 số nguyên u và v thể hiện 2 máy tính được nối với nhau bằng dây cáp.

Điều kiện:

• 1≤ N ≤ 3\times10^5.
• 1 ≤ u, v ≤ N, u != v

Số lượng hành trình tối ưu có độ dài chính xác là 2

Giải thích ví dụ 1: 3 Máy tính được kết nối có thể được biểu diễn như sau:

• Máy 1 kết nối với máy 2 và máy 3.
• Máy 2 chỉ kết nối với máy 1.
• Máy 3 chỉ kết nối với máy 1.

Hành trình tối ưu độ dài 2: Hành trình độ dài chính xác là 2 nghĩa là cần có 1 máy trung gian:

• 2→1→3: Đi từ 2 đến 3 qua máy trung gian 1.
• 3→1→2: Đi từ 3 đến 2 qua máy trung gian 1.

Hành trình không hợp lệ: 1→2→1, 1→3→1: Không được tính vì không cần phải đi qua máy trung gian (hành trình từ 1 đến 2 có thể trực tiếp).