Pilnie kvadrāti

Katrs pietiekami izglītots olimpietis zina, ka neorientēts grafs ir datu struktūra, kas sastāv no virsotnēm un šķautnēm, kur katra šķautne savieno divas virsotnes. Grafu sauc par sakarīgu, ja no jebkuras virsotnes var tikt līdz jebkurai citai, ejot pa šķautnēm.

Šķautņu kopu, pa kurām ejot var nokļūt no virsotnes $v_i$ līdz virsotnei $v_j$, sauc par ceļu starp šīm virsotnēm. Grafā ceļš, kas ir garāks par 0 un sākas un beidzas vienā un tajā pašā virsotnē, ir cikls. Sakarīgu grafu, kas nesatur ciklu, sauc par koku.

Šajā uzdevumā aplūkosim svarotus kokus - kokus, kur katrai šķautnei piekārtots kāds naturāls skaitlis $w_i$ (šķautnes svars). Patvaļīgām divām virsotnēm aplūkosim visu to šķautņu, kas atrodas uz īsākā ceļa starp šīm virsotnēm, svaru reizinājumu. Nepieciešams noteikt, cik atšķirīgiem virsotņu pāriem šis svaru reizinājums ir naturāla skaitļa kvadrāts.

Piemērā, kas parādīts attēlā, naturāla skaitļa kvadrāts ir svaru reizinājums uz deviņiem ceļiem: starp virsotnēm $1$ un $6$ ($3^2$), $1$ un $7$ ($6^2$), $1$ un $8$ ($18^2$), $2$ un $4$ ($2^2$), $2$ un $5$ ($4^2$), $4$ un $5$ ($2^2$), $6$ un $7$ ($6^2$), $6$ un $8$ ($18^2$), $7$ un $8$ ($18^2$).

Uzrakstiet datorprogrammu, kas dotam svarotam kokam nosaka to atšķirīgo virsotņu pāru, kuriem šķautņu svaru reizinājums uz ceļa starp šīm virsotnēm ir naturāla skaitļa kvadrāts, skaitu!

Pirmajā rindā dots koka virsotņu skaits - naturāls skaitlis $N$ ($2 \leq N \leq 2 \cdot 10^5$).

Nākamajās $N - 1$ rindās katrā doti trīs skaitļi $u_i$, $v_i$, $w_i$ ($u_i \neq v_i$, $1 \leq u_i, v_i \leq N$, $1 \leq w_i \leq 10^6$), kas norāda uz to, ka $i$-tā šķautne kokā savieno virsotnes $u_i$ un $v_i$ ar svaru $w_i$.

Izvaddatu vienīgajā rindā jābūt vienam nenegatīvam skaitlim - prasītajam pāru skaitam.