Reiz sensenos laikos Indulis atrada koku(Savienotu grafu, kur no katras virsotnes uz jebkuru citu virsotni pastāv tikai viens īsākais ceļš).

Uz šī koka katras šķautnes bija uzrakstīts kāds burts no a līdz h. Sauksim virsotņu pāri (x,y)(x!=y) par labu, ja, ejot no x uz y caur vienīgo īsāko ceļu, nekad neiziet cauri šķautnei, kuras burts ir mazāks par iepriekš izietās šķautnes burtu šajā ceļā.

Piemēram, ja iet cauri šķautnei, kas savieno (x,y), un tad cauri šķautnei, kas savieno (y,z), tad burtam uz (y,z) jābūt lielākam jeb vienādam, nekā burtam uz (x,y).  Ja nav iepriekšējā burta, tad ceļš joprojām ir labs. Burtu a sauc par lielāku nekā par burtu b, ja a atrodas tālāk alfabētā, nekā burts b.

Indulis saprata, ka manuāli labo virsotņu pāru skaitu ir grūti saskaitīt, tāpēc viņš prasa tavu palīdzību.

Pirmajā rindā dots n(2<=n<=100000) - koka virsotņu skaits.

Nākamajās n-1 rindās doti trīs skaitļi: u, v, c (1<=v,u<=n,u!=v), kas nozīmē, ka pastāv šķautne, kas savieno virsotnes u un v, un uz tās ir uzrakstīts burts c.

Garantēts, ka dotais burts c ir no 'a' līdz 'h' un ka grafs ir koks.

Jāizvada viens skaitlis - Labo pāru skaits.

Dotajā testa piemērā pastāv 9 labi virsotņu pāri: (1,2),(2,1),(1,3),(3,1),(1,4),(4,1),(2,3),(2,4),(3,4).