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 lângă 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:
- Pentru fiecare om, poate acesta să fie unul dintre cei infectați inițial?
- Pentru fiecare om, poate acesta să fie unul dintre cei neinfectați inițial?
Date de intrare
Pe prima linie se găsește 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
Se va afișa 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 și precizări
1 ≤ C ≤ 21 ≤ N ≤ 100 0000 ≤ M ≤ 100 000- 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.
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 ≤ 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 (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 (3 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
Exemple
stdin
1
6 5
1 1 0 0 1 1
4 3
3 6
1 2
5 6
3 4
stdout
110010
stdin
2
6 5
1 1 0 0 1 1
4 3
3 6
1 2
5 6
3 4
stdout
111101
Explicații
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ă.