Čikāgas gangsteri

Uzdevums

1920.gads Čikāgā: gangsteru kaujaslauks.

Ja divi gangsteri kaut reizi dzīvē ir satikušies, tie kļūst vai nu par draugiem līdz kapa malai vai arī par nāvīgākajiem ienaidniekiem. Gangsteri dzīvo -- un mirst -- saskaņā ar sekojošiem ētiskajiem principiem:

• Katrs mana drauga draugs ir arī mans draugs.
• Katrs mana ienaidnieka ienaidnieks ir mans draugs.

Divi gangsteri ir vienā bandā tad un tikai tad, ja viņi ir draugi.

Katrs gangsteris ir tieši vienas bandas loceklis.

Diemžēl jūs strādājat Čikāgas policijas departamentā. Jūsu uzdevums ir noteikt lielāko iespējamo bandu skaitu Čikāgā balstoties uz datiem, kas departamentam zināmi par personīgām attiecībām starp dažādiem gangsteriem.

Ievaddati

Faila gangs.in pirmajā rindā dots zināmo gangsteru skaits N (2 ≤ N ≤ 1000). Gangsteri ir numurēti ar naturāliem skaitļiem pēc kārtas no 1 līdz N. Faila otrajā rindā dots par gangsteriem zināmo faktu skaits M (1 ≤ M ≤ 5000).

Nākošajās M rindās dots šo faktu apraksts - pa vienam faktam katrā rindā. Katrs fakts ir formā F p q vai E p q, kur 1 ≤ p < q ≤ N ir divi attiecībā iesaistītie gangsteri. Visas trīs komponentes atdala tukšumsimboli. Ja pirmais simbols rindā ir F, tad šī rinda apraksta faktu, ka p un q ir draugi. Ja pirmais simbols ir E, tad šī rinda apraksta faktu, ka attiecīgie gangsteri ir ienaidnieki.

Uzskatiet, ka ievaddati vienmēr būs nepretrunīgi --- divi gangsteri nevar vienlaicīgi savā starpā būt gan draugi, gan ienaidnieki.

Izvaddati

Faila gangs.out vienīgajai rindai jāsatur viens naturāls skaitlis --- lielākais iespējamais bandu skaits.

Piemērs

gangs.in	gangs.out
6 4 E 1 4 F 3 5 F 4 6 E 1 2	3     Piezīme: Dotajā piemērā minētās trīs bandas ir: {1},{2,4,6},{3,5}.

Atsauces