== include(page="template/taskheader" task_id="saseg") ==

Plictisit de filantropie şi produs cipuri, William Poartă şi-a găsit o nouă pasiune: anchetele epidemiologice. Astfel, el s-a gândit să cerceteze răspândirea unui virus din trecut asupra omenirii, formată din N persoane.
William ştie pentru fiecare om starea sa finală (infectat sau neinfectat), însă nu ştie care dintre oameni au fost infectaţi iniţial, şi care au fost infectaţi de la alte persoane. Pe langă aceasta, el a aflat de la prietenul său Marcel Zahăr şi o serie de întâlniri (în ordine cronologică) ce au avut loc între câte 2 persoane prin care virusul s-a răspândit, în următorul fel: dacă vreunul dintre cei doi vine la întâlnire infectat, atunci acesta îl va infecta şi pe celălalt (dacă acesta nu era deja infectat).

Plictisit de filantropie şi produs cipuri, William Poartă şi-a găsit o nouă pasiune: anchetele epidemiologice. Astfel, el s-a gândit să cerceteze răspândirea unui virus din trecut asupra omenirii, formată din $N$ persoane.
William ştie pentru fiecare om starea sa finală (infectat sau neinfectat), însă nu ştie care dintre oameni au fost infectaţi iniţial, şi care au fost infectaţi de la alte persoane. Pe langă aceasta, el a aflat de la prietenul său Marcel Zahăr şi o serie de întâlniri (în ordine cronologică) ce au avut loc între câte $2$ persoane prin care virusul s-a răspândit, în următorul fel: dacă vreunul dintre cei doi vine la întâlnire infectat, atunci acesta îl va infecta şi pe celălalt (dacă acesta nu era deja infectat).

Acum William îşi pune următoarele întrebări:
1. Pentru fiecare om, poate acesta să fie unul dintre cei *infectaţi* iniţial?

h2. Subtaskuri

* *Subtask 1 (3 puncte)*

* *Subtask 1 (12 puncte)*

** Se garantează că toate persoanele au aceeaşi stare finală (toate sunt infectate sau toate sunt neinfectate).
* *Subtask 2 (8 puncte)*

** $C = 1, 1 ≤ N ≤ 100, 0 ≤ M ≤ 100$
** Numărul de persoane infectate în final $≤ 18$

* *Subtask 4 (27 puncte)*

* *Subtask 4 (17 puncte)*

** $C = 1, 1 ≤ N ≤ 5 000, 0 ≤ M ≤ 5 000$
* *Subtask 5 (28 puncte)*
** $C = 1, 1 ≤ N ≤ 100 000, 0 ≤ M ≤ 100 000$

* *Subtask 6 (3 puncte)*

* *Subtask 6 (4 puncte)*

** $C = 2, 1 ≤ N ≤ 18, 0 ≤ M ≤ 100$
* *Subtask 7 (4 puncte)*