Quân chăn bò

Quân là một sinh viên miền quê vừa lên Sài Gòn học. Ngoài giờ học, Quân thường phụ giúp gia đình chăn nuôi. Trong một lần chăn bò, Quân nhận thấy những đàn bò bị phân thành hai giống khác nhau: giống Charolais (lông trắng) và giống Angus (lông đen).

Quân quyết định đi bộ dọc theo các dãy chuồng bò — các chuồng được kết nối thành một cấu trúc cây (liên thông, không có chu trình). Mỗi lối đi giữa hai chuồng được gắn giá trị \(0\) nếu gặp bò giống Charolais và \(1\) nếu gặp bò giống Angus.

Quân muốn chọn một đường đi từ chuồng \(u\) đến chuồng \(v\) (hai chuồng khác nhau), rồi chọn một điểm dừng chân \(r\) (\(r \ne u, v\)) nằm trên đường đi đó để dừng nghỉ. Quân kỳ vọng rằng sẽ chọn một đường đi mà số lối đi gặp bò trắng và bò đen bằng nhau trên cả hai đoạn đường từ \(u\) đến \(r\) và từ \(r\) đến \(v\).

Yêu cầu: Bạn hãy đếm số đường đi \((u, v)\) mà Quân có thể chọn sao cho có ít nhất một điểm dừng giữa đường khiến đoạn trước và đoạn sau đều có số lượng lối đi của hai giống bò bằng nhau.

Input

• Dòng đầu tiên chứa số nguyên \(n\): số chuồng bò (\(1 \le n \le 10^5\)).
• Tiếp theo \(n - 1\) dòng, mỗi dòng có ba số nguyên \(a, b, t\) (\(1 \le a, b \le n\)) mô tả một lối đi giữa chuồng \(a\) và chuồng \(b\); \(t = 0\) nếu gặp bò Charolais (lông trắng), \(t = 1\) nếu gặp bò Angus (lông đen).

Output

In ra số đường đi thỏa mãn.

Scoring

• Subtask 1: \(n \le 100\).
• Subtask 2: \(n \le 10^3\).
• Subtask 3: \(n \le 10^5\).

Sample Input 1

7
1 2 0
3 1 1
2 4 0
5 2 0
6 3 1
5 7 1

Sample Output 1

1

Notes

Hai đường đi \((u, v)\) và \((v, u)\) chỉ được tính một lần. Một đường đi \((u, v)\) vẫn chỉ được tính một lần dù cho có nhiều điểm dừng chân thỏa mãn.

Ở ví dụ, đường đi duy nhất thỏa mãn là \(3 \to 1 \to 2 \to 5 \to 7\) với điểm dừng chân là chuồng \(2\): đoạn \(3 \to 1 \to 2\) gồm một lối đi loại \(1\) và một lối đi loại \(0\), đoạn \(2 \to 5 \to 7\) cũng vậy.