| Fişierul intrare/ieşire: | petrecere2.in, petrecere2.out | Sursă | Infoarena Monthly 2012, Runda 9 |
| Autor | Mihai Calancea, Mihai-Alexandru Dusmanu | Adăugată de |  Adrian Budau •freak93 |
| Timp execuţie pe test | 0.1 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Petrecere2
Intr-o zi eroul nostru Paftenie se hotaraste sa dea o petrecere. Acesta are la dispozitie N prieteni pe care ii poate invita. Mai stie despre ei M relatii de forma
- Al X-lea prieten nu vine decat daca vine si al Y-lea prieten(si viceversa)
- Al X-lea prieten nu vine daca vine al Y-lea prieten(si viceversa).
Paftenie mai stie ca daca 2 prieteni de-ai sai se afla in relatia de al doilea tip, trebuie neaparat sa il invite pe unul din ei altfel vor fi amandoi suparati.
Fiind un om de treaba Paftenie se hotaraste sa nu supere pe nimeni, totusi el doreste sa aiba cat mai multi prieteni la petrecerea sa.
El a incercat deja sa folosesasca un calculator pentru a afla cat de multi prieteni poate aduce la petrecerea sa, dar nu prea s-a descurcat, asa ca el va roaga pe voi sa faceti treaba asta in locul lui, promitandu-va ca va va invita si pe voi la petrecere daca reusiti.
Date de intrare
Fişierul de intrare petrecere2.in va contine M + 1 linii. Prima linie va contine exact doua numere naturale despartite printr-un singur spatiu N si M care reprezinta numarul de prieteni ai lui Paftenie, respectiv numarul de relatii pe care le stie Paftenie despre ei.
Urmatoarele M linii vor contine fiecare exact o relatie reprezentata prin 3 numere naturale T, X si Y. Daca T este 0 atunci se stie ca al X-lea prieten va veni la petrecere doar daca va veni si al Y-lea prieten(si reciproca), iar daca T este 1 atunci se stie ca X si Y nu pot fi amandoi prezenti la petrecere.
Date de ieşire
În fişierul de ieşire petrecere2.out trebuie sa se afle exact un singur numar natural reprezentand numarul maxim de prieteni pe care Paftenie ii poate avea la petrecere fara sa incale vreuna din cele M relatii.
Restricţii
- 2 ≤ N ≤ 100.000.
- 1 ≤ M ≤ 100.000.
- Se garanteaza ca Paftenie poate aduce cel putin pe cineva la petrecere.
- Paftenie nu stie neaparat astfel de relatii pentru toti prietenii sai
Exemplu
| petrecere2.in | petrecere2.out |
|---|---|
| 3 2 0 1 2 1 2 3 | 2 |
Explicaţie
Paftenie ii poate chema la petrecere fie numai pe prietenii cu indicii 1 si 2, fie numai pe prietenul cu indicele 3. El poate chema astfel maxim 2 prieteni.
