Fişierul intrare/ieşire:	saseg.in, saseg.out	Sursă	ONSEPI, clasele 11-12
Autor	Costin Oncescu	Adăugată de	Nicola Alexandra Mihaela •Nicolaalexandra
Timp execuţie pe test	0.125 sec	Limită de memorie	250000 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

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).
Acum William îşi pune următoarele întrebări:

1. Pentru fiecare om, poate acesta să fie unul dintre cei infectaţi iniţial?
2. Pentru fiecare om, poate acesta să fie unul dintre cei neinfectaţi iniţial?

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 ).
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.

Date de ieşire

În fişierul de ieşire saseg.out se va afla o singură linie conţinând N cifre binare neseparate prin spaţii, reprezentând răspunsul pentru respectivul test.
Dacă C = 1, se rezolvă prima cerinţă, iar al i-lea caracter va fi 1 dacă şi numai dacă există un scenariu iniţial în care persoana i este infectată care duce la scenariul final dat, altfel va fi 0.
Dacă C = 2, se rezolvă a doua cerinţă, iar al i-lea caracter va fi 1 dacă şi numai dacă există un scenariu iniţial în care persoana i este neinfectată care duce la scenariul final dat, altfel va fi 0.

Restricţii

• 1 ≤ C ≤ 2
• 1 ≤ N ≤ 100000
• 0 ≤ M ≤ 100000
• Se garantează că pentru fiecare test există un scenariu posibil iniţial care să ducă la scenariul final.
• Persoanele nu se pot infecta spontan. Acestea pot fi infectate la final doar dacă au fost infectate iniţial sau au fost infectate de o altă persoană în urma unei întâlniri.

Subtaskuri

• 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 ≤ 18, 0 ≤ M ≤ 100

• Subtask 3 (9 puncte)
  • C = 1, 1 ≤ N ≤ 100, 0 ≤ M ≤ 100
  • Numărul de persoane infectate în final ≤ 18

• 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 (4 puncte)
  • C = 2, 1 ≤ N ≤ 18, 0 ≤ M ≤ 100

• Subtask 7 (4 puncte)
  • C = 2, 1 ≤ N ≤ 100, 0 ≤ M ≤ 100
  • Numărul de persoane infectate în final ≤ 18

• Subtask 8 (7 puncte)
  • C = 2, 1 ≤ N ≤ 5 000, 0 ≤ M ≤ 5 000

• Subtask 9 (11 puncte)
  • C = 2, 1 ≤ N ≤ 100 000, 0 ≤ M ≤ 100 000

Exemplu

Explicaţie

Considerăm următoarele două scenarii iniţiale: 010010, 100010. Se poate observa uşor că ambele scenarii duc la starea finală 110011 în urma întâlnirilor.
Pentru persoanele 1, 2 şi 5 există scenarii în care acestea sunt infectate iniţial, şi se poate demonstra că pentru niciuna dintre persoanele 3, 4 şi 6 nu există vreun scenariu iniţial în care acestea să fie infectate.
Pentru persoanele 1, 2, 3, 4 şi 6 există scenarii în care acestea sunt neinfectate iniţial, şi se poate demonstra că pentru persoana 5 nu există vreun scenariu iniţial în care acesta să fie neinfectată.

Cum se trimit solutii?