Фермер Джон планирует утренную прогулку по ферме. Ферма имеет структуру как дерево: имеется N амбаров (1 <= N <= 100,000), которые соединены N-1 дорожками по которым можно ойти о одного амбара в другой. ФД хочет выбрать путь, который начнется и закончится в различных амбарах, так чтобы не проходить ни по какой дорожке дважды. Поскольку путь может оказаться слишком длинным, он хочет определить "амбар отдыха", который лежит на пути и отличается от стартового и конечного амбаров.
Вдоль каждой дорожки гуляет стадо белых или стадо черных коров. Поэтому ФД хочет выбрать такой путь, чтобы он прошел одинаковое количество белых и черных стад в обоих случаях - и на пути от старта к "амбару отдыха", и на пути от "амбара отдыха" к финишу.
ФД интересуется сколько существует различных путей, обладающих свойствами, описанными выше. Два пути различаются, если они содержат различные множества дорожек. Путь должен считаться один раз, даже если может быть множество "амбаров отдыха" на этом пути. Вычислите это количество для ФД.
PROBLEM NAME: yinyang
Формат входных данных
* Строка 1: Целое число N.
* Строки 2..N: Три целых числа ai, bi и ti, представляющих два амбара, которые соединяет эта дорожка. t0 равно 0 если вдоль дорожки пасутся белые коровы и 1, если черные.
Формат выходных данных
* Строка 1: Одно целое число, представляющее количество возможных путей ФД
Примечание
Никакой из путей длины 2 не имет подходящегоамбара для остановки. Поэтому должны рассматривать только пути длины 4. Единственный подходящий путь 3-1-2-5-7 с остановкой в 2.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
7
1 2 0
3 1 1
2 4 0
5 2 0
6 3 1
5 7 1
|
1
|