Корневым деревом называется связный граф без циклов с выделенной вершиной. В рамках данной задачи будем считать, что корнем дерева всегда является вершина с номером 1.
Наименьшим общим предком вершин u и v называется наиболее удалённая от корня дерева вершина, лежащая как на пути от корня до u, так и на пути от корня до v. Будем обозначать наименьшего общего предка вершин u и v как LCA(u, v).
У белочки Сенди было корневое дерево, состоявшее из n вершин, в которых она хранила свои орешки. К несчастью, подводный шторм разрушил это дерево, и теперь Сенди никак не может его восстановить. Она смогла назвать m рёбер своего дерева и q троек чисел ai, bi и ci, про которые она полагает, что LCA(ai, bi) = ci.
Помогите Сенди посчитать, сколько существует деревьев с корнем в вершине 1, про которые верна вся информация, названная Сенди. Если же она что-то напутала, и таких деревьев не существует, то выведите 0. Два корневых дерева считаются различными, если существует хотя бы одно ребро, принадлежащее одному из этих деревьев и не принадлежащее другому.
Выходные данные
Выведите количество деревьев размера n с корнем в вершине 1, таких что для них верна вся информация, которую помнит Сенди.
Примечание
Во втором примере правильный ответ выглядит так:
В третьем примере возможны два правильных ответа:
В четвёртом примере несложно заметить, что информация, предоставленная Сенди, противоречива.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 0 0
|
16
|
|
2
|
4 0 1
3 4 2
|
1
|
|
3
|
3 1 0
1 2
|
2
|
|
4
|
3 0 2
2 3 2
2 3 1
|
0
|
|
5
|
4 1 2
1 2
2 2 2
3 4 2
|
1
|