Cho đồ thị ~T~ dạng cây gồm ~n~ đỉnh được đánh số từ ~1~ đến ~n~.

Một đoạn ~[l,r]~ ~(1 \le l \le r \le n)~ được gọi là đoạn liên thông nếu thỏa mãn:

• Xây dựng đồ thị ~G~ với tập đỉnh ~V= \{i \; | \; i \in [l,r]\}~, hai đỉnh ~i~ và ~j~ có cạnh nối trong ~G~ khi và chỉ khi ~i~ và ~j~ cũng có cạnh nối trong ~T~. Khi đó, đồ thị ~G~ là một đồ thị liên thông.

Ví dụ, với đồ thị ~T~ dạng cây như sau:

Xét đoạn ~[l,r]=[1,3]~, đồ thị ~G~ có tập đỉnh ~V=\{1,2,3\}~ và hai cạnh ~1-2~, ~2-3~.

Khi đó, đồ thị ~G~ là đồ thị liên thông và đoạn ~[l,r]=[1,3]~ là một đoạn liên thông.

Xét đoạn ~[l,r]=[3,4]~, đồ thị ~G~ có tập đỉnh ~V=\{3,4\}~ và không có cạnh nối.

Khi đó, đồ thị ~G~ không liên thông và đoạn ~[l,r]=[3,4]~ không phải là một đoạn liên thông.

Yêu cầu: Cho biết đồ thị ~T~. Hãy đếm số đoạn liên thông ~[l,r]~ ~(1 \le l \le r \le n)~.

Input

• Dòng đầu tiên chứa số nguyên ~n~ ~(1 \le n \le 10^6)~.
• ~n-1~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~u~ và ~v~ mô tả cạnh nối ~u-v~ của cây ~(1 \le u,v \le n~ ; ~u \neq v)~
• Dữ liệu đảm bảo đồ thị ~T~ là một đồ thị dạng cây hợp lệ.

Output

• In ra số đoạn liên thông.

Examples

Sample Input

4
1 2
2 3
2 4

Sample Output

9

Scoring

• Subtask ~1~ ~-~ ~750~ điểm: ~n \le 40~
• Subtask ~2~ ~-~ ~750~ điểm: ~n \le 400~
• Subtask ~3~ ~-~ ~750~ điểm: ~n \le 4000~
• Subtask ~4~ ~-~ ~750~ điểm: Không có ràng buộc gì thêm

Notes

Trong ví dụ, tất cả các đoạn ~[l,r]~ ~(1 \le l \le r \le 4)~ ngoại trừ đoạn ~[l,r]=[3,4]~ đều là đoạn liên thông.