Три-бітний комп'ютер завдає удару у відповідь
Комп'ютер з трьома бітами виявився величезним провалом, незважаючи на постійні зусилля провідних вчених Байтленду. Але тепер у них є нова ідея: Квантовий Комп'ютер на Три Біти (ККТБ). Тепер ТБК можна вважати лише підготовкою до справжньої справи - ККТБ.
Вчені прогнозують, що нова машина матиме велику потужність, бла-бла, ще багато складних проблем для вирішення, бла-бла. Тепер перейдемо до суті.
Процедура ініціалізації знову є головною проблемою, але з квантовими комп'ютерами це зовсім інша історія. Проблема полягає в тому, що будь-яка дія має побічні ефекти, тобто впливає на все інше. Це займає багато часу, і ініціалізація пам'яті по біту просто неможлива. Але є інший підхід. Вчені розробили великомасштабні контрольовані імпульси (ВКІ), які впливають на всі біти пам'яті одночасно, і, більше того, точно відомо, який вплив вони мають. Вони також дуже швидкі, тому випромінювання навіть великої кількості імпульсів краще, ніж ініціалізація пам'яті по біту. Перше питання, яке потрібно розглянути, це чи існує послідовність імпульсів, яка обнулить всю пам'ять. Ваше завдання - написати комп'ютерну програму, щоб відповісти на це питання.
Більш формально, кожен біт пам'яті може бути в одному з n станів, пронумерованих 0, ..., n-1. Імпульс ВКІ f змінює всі біти однаково, тобто його можна розглядати як функцію f: {0, ..., n-1} → {0, ..., n-1}. Наприклад, f(3) = 5 означає, що якщо імпульс f випромінюється, то кожен біт у стані 3 змінить свій стан на 5. Вчені знають, як випромінювати кілька імпульсів f_1, ..., f_k. Вам потрібно з'ясувати, чи існує послідовність імпульсів, яка приведе всі біти в стан 0 незалежно від їх початкового стану.
Завдання
Написати програму, яка:
зчитує описи доступних імпульсів,
перевіряє, чи можливо обнулити пам'ять,
записує відповідь у вихідний файл.
Вхідні дані
Вхідний файл може містити кілька тестових випадків. Перша строка вхідного файлу містить одне додатне ціле число T, (1≤ T ≤ 10), кількість тестових випадків. Опис тестових випадків слідує далі. Опис одного тестового випадку починається з рядка, що містить два додатних цілих числа n, k,(1 ≤ n ≤ 200, 1 ≤ k ≤ 5), де n - кількість різних станів бітів пам'яті, а k - кількість різних імпульсів, які можуть бути випромінені. Наступні k рядків містять опис імпульсів, i-й рядок містить опис i-го імпульсу. Опис імпульсу f - це послідовність цілих чисел f(0) ... f(n-1), що описують вплив f на стан будь-якого біта пам'яті. Ці цілі числа розділені одним пробілом.
Вихідні дані
Вихідний файл повинен містити T рядків, по одному для кожного тестового випадку. i-й рядок повинен складатися з одного слова YES, якщо обнулення пам'яті в i-му тестовому випадку можливе, або NO в іншому випадку.