Gaujos

Užduotis

Čikaga, 1920-ieji metai: gangsterių gaujų tarpusavio mūšio laukas.

Jei du gangsteriai kada nors buvo susitikę, jie arba tapo neišskiriamais draugais, arba mirtinais priešais. Gangsteriai gyvena (ir miršta) pagal tokias etikos normas:

1. Mano draugo draugas yra mano draugas.
2. Mano priešo priešas yra mano draugas.

Du gangsteriai priklauso tai pačiai gaujai jei ir tik jei jie yra draugai.

Jums labai nepasisekė, nes jus pasamdė Čikagos policijos departamentas. Remiantis policijos duomenimis apie žinomus gangsterių tarpusavio santykius, jums reikia suskaičiuoti, kiek daugiausiai skirtingų gaujų gali būti Čikagoje.

Pradiniai duomenys

Pirmoje pradinių duomenų failo eilutėje įrašytas gangsterių skaičius N (2 <= N <= 1000). Antroje eilutėje įrašytas žinomų faktų apie gangsterių tarpusavio santykius skaičius M (1 <= M <= 5000).

Tolesnėse M eilučių pateikiami faktai, kiekvienam faktui skiriant po vieną eilutę. Kiekvienas faktas užrašomas pavidalu „F p q“ arba „E p q“. p ir q – tai du gangsteriai (skaičiai tarp 1 ir N), kurių santykius apibūdina šis faktas. Jei pirmoji eilutės raidė yra F, tai reiškia, kad p ir q yra draugai (friends), o jei E – tai p ir q yra priešai (enemies).

Pradiniai duomenys yra neprieštaringi. T.y. du gangsteriai nebus ir draugai, ir priešai.

Rezultatai

Pirmoje ir vienintelėje rezultatų failo eilutėje reikia įrašyti maksimalų skirtingų gaujų skaičių.

Pavyzdys

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

3

Pavyzdį atitinka šios trys gaujos: {1}, {2, 4, 6} ir {3, 5}.