Nosaukums
Čikāgas gangsteri (gangs)
Laika limits
1.00s
Atmiņas limits
256.0 MB

Definīcija

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. 


Ievaddatu raksturojums

Ievaddatu 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 < qN 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.


Izvaddatu raksturojums

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


Piezīmes

Uzdevums izmantots Baltijas 9 .informātikas olimpiādē Tartu(Igaunija) 2003.gadā


Paraugdati

Stdin
6
4
E 1 4
F 3 5
F 4 6
E 1 2
Stdout
3

Uzdevums tiek aizsargāts ar autortiesībām un tā kopēšana vai neatļauta izmantošana ir aizliegta.