Tại thành phố cây, có \(N\) điểm du lịch hấp dẫn được đánh số từ \(1\) đến \(N\). Thành phố có \(N-1\) con đường \(2\) chiều để nối các điểm du lịch. Thị trưởng thành phố phát hiện ra là việc tổ chức các tour đi từ địa điểm \(u\) đến các địa điểm được đánh số là bội của nó sẽ rất thú vị, các tour như vậy thì du khách sẽ được thăm tất cả các địa điểm trên đường đi đơn giữa 2 địa điểm này. Hỏi với tất cả cách tổ chức tour như vậy thì tổng số địa điểm được thăm là bao nhiêu?

Dữ liệu

• Dòng đầu tiên là số địa điểm du lịch \(N\) của thành phố (\(1≤N≤10^5\))
• \(N-1\) dòng tiếp theo thể hiện đường nối giữa các thành phố

Kết quả

• Ghi tổng số địa điểm du lịch được thăm với tất cả các tour được xây dựng.

Input

10
3 4
3 7
1 4
4 6
1 10
8 10
2 8
1 5
4 9

Output

55

Giải thích: Chúng ta có tất cả các con đường và số địa điểm có thể thăm được như sau:

\(1→2=4 ; 1→3=3; 1→4=2; 1→5=2; 1→6=3;\)
\(1→7=4; 1→8=3; 1→9=3; 1→10=2; 2→4=5;\)
\(2→6=6; 2→8=2; 2→10=3; 3→6=3;\)
\(3→9=3; 4→8=4 ; 5→10=3.\)

Do đó tổng số địa điểm du lịch được thăm sẽ là: \(55\).

Nguồn: CD DHBB 2020