== 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. Date de intrare
Fişierul de intrare $saseg.in$ conţine pe prima linie un număr întreg $C$, reprezentând numărul cerinţei de rezolvat. Pe cea de-a doua linie se găsesc două numere întregi $N$, $M$, reprezentând numărul de persoane, respectiv numărul de întâlniri care au loc.

Pe cea de-a treia linie se găsesc $N$ numere (având valori între $0$ şi $1$) *separate* prin spaţii, reprezentând pentru fiecare om starea sa finală ( $0$ - neinfectat, $1$ - infectat ).

Pe cea de-a treia linie se găsesc $N$ numere (având valori între $0$ şi $1$) *separate* prin spaţii, reprezentând pentru fiecare om starea sa finală ($0$ - neinfectat, $1$ - infectat).

Următoarele $M$ linii reprezintă fiecare câte o întâlnire (în ordine cronologică), având $2$ numere întregi distincte (între $1$ şi $N$) reprezentând cele $2$ persoane care se întâlnesc.
h2. Date de ieşire

h2. Subtaskuri

* *Subtask 1 (12 puncte)*

* *Subtask 1 (3 puncte)*
** $C = 1$

** 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 (17 puncte)*

* *Subtask 4 (27 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 (4 puncte)*

* *Subtask 6 (3 puncte)*

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