AlgoLiga 2018

Stawy i grobla

Łamigłówka stawy i grobla znana także pod nazwą nurikabe, to łamigłówka pochodząca od wydawnictwa Nikoli. Początkowo diagram w niektórych polach zawiera liczby, które są częścią stawu złożonego z tylu pól, jaka jest wartość tej liczby. Wszystkie stawy są wielobokami rozdzielonymi groblą, która tworzy jedną spójną figurę. Częścią grobli nie może być kwadrat złożony z czterech pól 2×2. Zadanie polega na takim zaczernieniu pól tworzących groblę, aby powstałe w ten sposób stawy były rozłączne, tzn. nie były połączone bokami. Twoim zadaniem jest rozstrzygnąć, na podstawie podanego diagramu, czy łamigłówka jest rozwiązana, czy też nie. Każdy diagram opisany jest za pomocą znaków x i . oraz liczb z przedziału [1-9]. Znak x oznacza pole zaczernione należące do grobli, liczby od 1 do 9 to pola, które są częścią stawu, o których mowa wyżej, a znak .(kropka) jest polem niezaczernionym należącym do stawu.

Wejście
W pierwszym wierszu wejścia znajduje się liczba przypadków testowych d (d ≤ 100). Każdy przypadek opisują w pierwszym wierszu dwie liczby całkowite m, n (4 ≤ m,n ≤ 100) oznaczające wymiary diagramu. Dalej podanych jest n wierszy, każdy po m znaków opisujących diagram według specyfikacji podanej w treści zadania. Należy założyć, że wszystkie diagramy podane na wejściu są poprawne.

Wyjście
Dla każdego przypadku testowego należy wypisać TAK albo NIE, w zależności czy łamigłówka jest rozwiązana, czy też nie.

Przykład

Wejście

3
6 5
2.xxx1
xxx.xx
x3x2x.
x..xx.
xxxx4.
6 5
2.xxx1
xxx.xx
x3x2x.
...xx.
xxxx4.
6 5
2.xxx1
xxx..x
x3x3x.
x..xx.
xxxx4.

Wyjście
TAK
NIE
NIE