Сума XOR

Задано дерево з $n$ вершинами. Ребра дерева мають вагу лише $0$ або $1$. Знайдемо XOR суму між усіма парами вершин. Обчисліть суму усіх XOR сум.

Вхідні дані

Перший рядок містить кількість вершин у графі $n(2\le n\le 10^5)$. Наступні $n-1$ рядків описують ребра. Кожен рядок містить три цілих числа: номери вершин, що з'єднані ребром (вершини нумеруються числами від $1$ до $n$), та вагу ребра ($0$ або $1$).

Вихідні дані

Виведіть суму XOR сум між усіма парами вершин.

Приклади