Тріоміно#3035

Тріоміно

1 секунда

64 мегабайти

Легка

Тріоміно — це зв'язна фігура, що складається з трьох квадратів. Існують лише два різних типи таких фігур, як показано на малюнку. Усі інші тріоміно — це просто обертання цих двох.

Прямокутне поле з $m$ рядками і $n$ стовпцями вважається заповненим тріоміно, якщо:

Кожне тріоміно повністю розташоване в межах поля та покриває рівно три клітинки.
Тріоміно не перетинаються між собою.
Не більше двох клітин залишаються порожніми (не покриті тріоміно).

Поле, заповнене тріоміно, можна уявити у вигляді прямокутної таблиці. Значення $0$ позначає порожню (незаповнену) клітинку. Однакові натуральні числа вказують, що клітинки належать до одного й того ж тріоміно, а різні значення — до різних тріоміно.

Напишіть програму, яка, проаналізувавши вміст декількох числових двовимірних таблиць, визначає для кожної з них, чи є вона правильно заповненим прямокутним полем тріоміно.

Вхідні дані

У першому рядку міститься кількість прямокутних таблиць $t$ ( $2 \leq t \leq 10$ 2 \le t \le 10). Далі йдуть $t$ блоків такої структури. У першому рядку кожного блоку записано два цілі числа $m$ і $n$ ( $1 \leq m \leq 200$ 1 \le m \le 200, $1 \leq n \leq 200$ 1 \le n \le 200) — кількість рядків та стовпців відповідної таблиці. Потім йдуть $m$ рядків по $n$ цілих чисел у кожному. Значення цих чисел лежать у межах від $0$ до $⌊ \frac{mn}{3} ⌋$ \left\lfloor \frac{mn}{3} \right\rfloor включно. Обсяг вхідних даних не перевищує $512$ Кб.

Вихідні дані

Виведіть $t$ рядків, у кожному з яких повинно міститися слово YES або NO (великими латинськими літерами), що вказує, чи є відповідна таблиця коректно заповненим прямокутним полем тріоміно.

Примітка: зображення для першого блоку:

Приклади

Приклад 1