Infomatrix




Se consideră o tablă împărțită în mai multe celule care conțin pioni. Celulele sunt conectate între ele prin săgeți, și mergând de la orice celulă în direcția în care indică săgețile nu vom ajunge niciodată în locul din care am plecat. Deci, există celule din care nu pleacă săgeți și celule în care nu ajung săgeți.
     Considerăm doi jucători. Fiecare jucător poate muta, când îi vine rândul, un pion din celula în care se află într-o celulă spre care pleacă o săgeată.
     Cel care nu mai poate muta atunci când îi vine rândul pierde partida.
     La începutul unui joc, prima mutare o face jucătorul 1.
     Să se determine dacă jucătorul 1 are strategie sigură de câștig.

Fișierul de intrare PAWNS.IN conține pe prima linie două numere întregi n și m, separate printr-un singur spațiu, care reprezintă numărul de celule de pe tablă, respectiv numărul de săgeți.
    Pe fiecare dintre următoarele m linii se află câte două numere întregi x și y, separate între ele printr-un singur spațiu, cu semnificația că există o săgeată care pleacă din celula cu numărul de ordine x și ajunge în celula cu numărul de ordine y.
    Pe linia următoare se află un număr t care reprezintă numărul de jocuri care se joacă.
    Pe fiecare dintre următoarele t linii se află n numere întregi, separate între ele prin spații, care reprezintă numărul de pioni din fiecare celulă pentru un anumit joc.


Fișierul de ieșire PAWNS.OUT trebuie să conțină t linii. Fiecare dintre cele t linii va conține valoarea 0, dacă pentru o configurație jucătorul 1 nu are strategie sigură de câștig și valoarea 1 în caz contrar.

  • 1 ≤ n, m ≤ 500;
  • 1 ≤ t ≤ 15;
  • numărul de pioni dintr-o celulă nu va depăși valoarea 500;
  • celulele sunt numerotate de la 1 la n.


  • PAWNS.IN
    3 3
    1 2
    1 3
    2 3
    2
    1 0 0
    2 2 2


    PAWNS.OUT
    1
    0