Državno natjecanje iz informatike 2017. / Srednja škola / Prva podskupina (1. i 2. razred) / drugi dan- 2. zadatak

Mirko igra igru spajanja riječi. U toj igri, riječ je niz od najmanje jednog i najviše 15 malih slova engleske abecede.

Ako su a i b proizvoljne riječi, onda kažemo da je b spojka od a ako je neki sufiks od a ujedno i prefiks od b, odnosno ako postoji riječ c takva da a završava na c i b počinje na c.

Tako je, primjerice, riječ “mirko” spojka od riječi “branimir”. Ako su a i b jednake onda je b također i spojka od a.

Zadan je niz od n riječi w1, w2, . . . , wn. Odredite koliko postoji parova (i, j), takvih da je wj spojka od wi, gdje su i i j različiti indeksi oba između 1 i n uključivo.

Ulazni​ podaci

U prvom redu nalazi se prirodni broj n (1 ≤ n ≤ 50 000) — broj riječi. U j-tom od sljedećih n redova nalazi se riječ wj — niz od najmanje jednog i najviše 15 malih slova engleske abecede.

Dozvoljeno je da se ista riječ pojavljuje više puta u ulazu.

Izlazni podaci

U prvi red ispišite traženi broj parova indeksa.

Primjeri test​ podataka

Ulaz

2
abcd
abab

Izlaz

1

Ulaz

3
abradabra
abra
rabra

Izlaz

6

Objašnjenje

Pojašnjenje drugog primjera: Svih 6 parova indeksa (i, j), takvih da je wj spojka od wi su dani u sljedećoj tablici:

Ulaz

4
xyz
xyz
xyz
z

Izlaz

9