Sudoku jest łamigłówką, której celem jest wypełnienie kwadratowego diagramu rozmiaru N²×N² liczbami naturalnymi z zakresu od 1 do N² w taki sposób, aby każdy wiersz, każda kolumna oraz każdy z N² wyróżnionych kwadratów rozmiaru N×N (zwanych „blokami” lub „podkwadratami”) zawierały dokładnie jedno wystąpienie każdej z liczb z zakresu od 1 do N². Każdy z kolejnych N² wierszy zawiera N² liczb naturalnych z zakresu od 1 do N². Jako wynik program powinien wydrukować na standardowym wyjściu słowo TAK jeśli wczytany diagram jest poprawnym rozwiązaniem sudoku oraz NIE w przeciwnym przypadku.

Przykładem prawidłowo rozwiązanego sudoku rozmiaru 2²x2² jest:

Natomiast przykładem prawidłowo rozwiązanego sudoku rozmiaru 3²x3² jest:

Napisz program, który dla wczytanego ze standardowego wejścia diagramu rozmiaru N²×N² zweryfikuje czy jest on poprawnym rozwiązaniem sudoku.

Specyfikacja wejścia i wyjścia

Pierwszy wiersz wejścia zawiera liczbę naturalną 1≤N≤10. Każdy z kolejnych N² wierszy zawiera N² liczb naturalnych z zakresu od 1 do N². Jako wynik program powinien wydrukować słowo TAK jeśli wczytany diagram jest poprawnym rozwiązaniem sudoku oraz słowo NIE w przeciwnym przypadku.

Przykładowe wejście I

2
1 2 3 4
3 4 1 2
2 3 4 1
4 1 2 3

Przykładowe wyjście I

TAK

Przykładowe wejście II

3
1 2 3 4 5 6 7 8 9
2 3 4 5 6 7 8 9 1
3 4 5 6 7 8 9 1 2
4 5 6 7 8 9 1 2 3
5 6 7 8 9 1 2 3 4
6 7 8 9 1 2 3 4 5
7 8 9 1 2 3 4 5 6
8 9 1 2 3 4 5 6 7
9 1 2 3 4 5 6 7 8

Przykładowe wyjście II

NIE