De Crăciun la grădiniţa Pinochio se organizează o serbare. În cadrul acestei serbări copii alcătuiesc o horă. Educatoarea doreşte ca la un semn făcut de ea să iasă din horă unii copii astfel incat sa se obţina o noua hora în care să nu existe doi băieţi sau două fete una lângă alta. Hora este dată prin prenumele (unul singur) al fiecărui copil, băieţii având la sfârşit caracterul '*'. Aceste prenume sunt separate prin unul sau mai multe spaţii.

Cerinţă

Să se scrie un program care să determine minim de copii care trebuie să iasă din horă pentru a respecta cerinţa din enunţ.

Date de intrare

Fişierul de intrare hora.in are pe prima linie şirul de caractere cu numele copiilor.

Date de ieşire

Fişierul de ieşire hora.out va conţine pe prima linie numărul cerut.

Restricţii

• Şirul de caractere din fişierul de intrare este alcătuit din maxim 145000 caractere, litere mari şi mici ale alfabetului englez, spaţii şi caracterul * (folosit numai pentru sfârşitul prenumelui băieţilor).
• Numele copiilor nu au mai mult de 8 litere.
• Ultimul copil este legat în horă de primul.
• Hora are cel puţin un băiat şi cel puţin o fată

Exemple

hora.in	hora.out	Explicaţii
Alin* Dan* Maria Anca Florinel* Dan*	4	De exemplu se pot elimina din horă copii Alin, Maria, Florinel, Dan, rămânând o horă doar cu Dan şi Maria.

prof. Doru Popescu Anastasiu

C. N. "Radu Greceanu" Slatina

dopopan@yahoo.com