Выполнимость снова!
Алиса недавно начала работать над аппаратной разработкой компании, ее работа состоит в определении дефектов в готовых интегральных схемах. Выявление этих дефектов сводится к решению задачи выполнимости. Помогите Алисе написать программу, которая решает эту задачу.
Входные данные
Первая строка содержит количество тестов, не большее 5. Первая строка каждого теста содержит два числа n (1 ≤ n ≤ 20) и m (1 ≤ m ≤ 100), где n - количество переменных, а m - количество правил. Каждая из следующих m строк задает одно правило. Каждое правило представляет собой дизъюнкцию литералов вида X[i] или ~X[i] для некоторого i (1 ≤ i ≤ n), где ~X[i] обозначает отрицание литерала X[i]. Оператор "or" обозначается символом v и отделяется от литералов одним пробелом.
Выходные данные
Для каждого теста вывести в отдельной строке satisfiable если формула выполняемая и unsatisfiable иначе.