== include(page="template/taskheader" task_id="binar2") ==
== include(page="template/taskheader" task_id="petrecere2") ==
Poveste şi cerinţă...
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).
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.
h2. Date de intrare
Fişierul de intrare $binar2.in$ ...
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.
h2. Date de ieşire
În fişierul de ieşire $binar2.out$ ...
Î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.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $2 ≤ N ≤ 100.000$.
* $1 ≤ M ≤ 100.000$.
* Se garanteaza ca sistemul admite cel putin o solutie.
* In cele $M$ ecuatii nu apar neaparat informatii despre toate cele $N$ variabile.
h2. Exemplu
table(example). |_. binar2.in |_. binar2.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 3 2
0 1 2
1 2 3
| 2
|
h3. 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.
== include(page="template/taskfooter" task_id="binar2") ==
== include(page="template/taskfooter" task_id="petrecere2") ==
