Fişierul intrare/ieşire:petrecere2.in, petrecere2.outSursăInfoarena Monthly 2012, Runda 9
AutorMihai Calancea, Mihai-Alexandru DusmanuAdăugată defreak93Budau Adrian freak93
Timp execuţie pe test0.2 secLimită de memorie16384 kbytes
Scorul tăuN/ADificultateN/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.inpetrecere2.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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content