Gica si Petrica locuiesc in Orasul Vesel. Acolo exista o retea stradala care contine doar strazi cu sens unic iar pentru a te deplasa intre doua intersectii trebuie sa platesti o taxa specifica fiecarei intersectii si fiecarei strazi prin care treci (inclusiv intersectia din care pleci si intersectia in care ajungi). Aceste taxe nu deranjeaza insa pe nimeni, deoarece sunt valori monetare naturale intre $0$ si {$10$}. Pe cei doi nu ii intereseaza harta propriu-zisa a Orasului, insa au gasit tabelul sumelor minime pe care trebuie sa le plateasca pentru a se plimba intre oricare doua intersectii si s-au gandit sa-l foloseasca pentru a juca un joc interesant (Aceasta matrice contine numai valori finite).

Astfel, avand matricea $A$ in care {$A{~i,j~}$} reprezinta costul minim pentru a ajunge din intersectia $i$ in intersectia $j$ ({$A{~i, i~}$} este taxa care trebuie platita in nodul {$i$}), fiecare dintre cei doi muta alternativ, dupa cum urmeaza: jucatorul aflat la mutare isi alege un numar natural strict pozitiv {$k$}, si scade $k$ din toate elementele unei linii sau coloane ale matricei, cu conditia ca toate elementele matricei sa ramana nenegative. Gica muta primul, iar jucatorul care, atunci cand ii vine randul, nu mai poate efectua o mutare corecta, pierde. Se considera ca cei doi prieteni joaca perfect, insemnand ca daca unul dintre ei are la un moment dat o strategie de castig indiferent de mutarile adversarului, nu va efectua o mutare care sa duca la pierderea oricarei strategii de castig.

Astfel, avand matricea $A$ in care {$A{~i,j~}$} reprezinta costul minim pentru a ajunge din intersectia $i$ in intersectia $j$ ({$A{~i,i~}$} este taxa care trebuie platita in nodul {$i$}), fiecare dintre cei doi muta alternativ, dupa cum urmeaza: jucatorul aflat la mutare isi alege un numar natural strict pozitiv {$k$}, si scade $k$ din toate elementele unei linii sau coloane ale matricei, cu conditia ca toate elementele matricei sa ramana nenegative. Gica muta primul, iar jucatorul care, atunci cand ii vine randul, nu mai poate efectua o mutare corecta, pierde. Se considera ca cei doi prieteni joaca perfect, insemnand ca daca unul dintre ei are la un moment dat o strategie de castig indiferent de mutarile adversarului, nu va efectua o mutare care sa duca la pierderea oricarei strategii de castig.

h2. Cerinta