Ielele

Ielele s-au întâlnit în clar de lună pentru horă. Dar vai, pădurea lor fermecată a fost tăiată de săteni, pentru lemne de foc. Furioase, ielele vor să se răzbune.

În poiana în care ielele trăiesc există $N$ sate, conectate prin $N - 1$ drumuri, în așa fel încât din oricare sat se poate ajunge în oricare alt sat. Fiecare drum are o lungime, exprimată ca un număr natural între $1$ și $M$.

Ielele se întreabă: Câte parcursuri există între sate, pentru care lungimile drumurilor formează o permutare a numerelor de la $1$ la $M$?

Un parcurs este o cale între două sate care urmează drumurile fără a trece de două ori prin același drum. Cu alte cuvinte, este o succesiune de drumuri care leagă două sate fără a face bucle sau a se întoarce. Un parcurs este considerat egal cu parcursul invers.

Ajutați-le să calculeze numărul de parcursuri posibile.

Date de intrare

Pe prima linie se găsesc numerele $N$ și $M$, cu semnificația din enunț.

Pe următoarele $N - 1$ linii se găsesc câte 3 numere $A$, $B$ ($1 \leq A, B \leq N$) și $L$ ($1 \leq L \leq M$), semnificând că există un drum de lungime $L$ între satul $A$ și satul $B$.

Date de ieșire

Pe unica linie afișati numărul cerut.

Restricții și precizări

• $1 \leq N \leq 10^5$.
• $1 \leq M < N$.
• Se garantează că datele din input sunt corecte.

Exemplul 1

stdin

6 3
1 2 1
2 3 2
3 4 3
3 5 1
2 6 3

stdout

2

Explicație

Există două parcursuri valide:

• Parcursul $6 - 2 - 3 - 5$, și
• Parcursul $4 - 3 - 2 - 1$.

Nu există niciun alt parcus ale cărui lungimi de drumuri să formeze o permutare a numerelor de la $1$ la $3$.