Современный мир немыслим без Интернета и электронной почты. Для того, чтобы людям было проще ориентироваться в потоке поступающих писем, были созданы специальные программы - почтовые клиенты. Фирма TIRLABS занимается разработкой почтового клиента The Bar!.
Недавно программисты компании завершили разработку очередной, 366239-ой, версии этого почтового клиента. Менеджеры по продажам и рекламе уже готовы вовсю рекламировать и продавать эту новую программу. Однако, генеральный директор компании TIRLABS считает, что любая программа должна быть подвергнута всестороннему тестированию, прежде чем она будет продаваться. «Да и не работающую программу, скорее всего, никто не купит!» - сказал он.
Одним из видов тестирования сложных программ является так называемое стресс-тестирование. При нем программа тестируется в экстремальных условиях, часто даже в таких, на какие она не рассчитана. Для тестирования The Bar! ver. 366239 был выбран такой метод: программа запускается на n компьютерах, стоящих в одной комнате, после чего с компьютеров друг на друга посылается m писем. При этом никакие два события (отправление или прием письма) не происходят одновременно, а сеть настолько надежна, что все письма доходят до адресата. Адресат у каждого письма при этом только один.
Почтовый клиент The Bar! в процессе работы ведет протокол, в который заносятся идентификаторы отправленных и полученных писем в том порядке, в котором они были обработаны почтовым клиентом. При этом при оценке результатов тестирования в расчет принимаются только события, отраженные в этом протоколе.
Программа считается правильно работающей по результатам тестирования, если всем событиям, указанным в протоколах, можно сопоставить моменты времени таким образом, что никакие два события не происходят одновременно, и каждое из писем отправляется до того, как получается. При этом, разумеется, внутри каждого из протоколов порядок событий должен остаться прежним.
Даны протоколы работы почтового клиента на каждом из компьютеров. Напишите программу, проверяющую, можно ли по результатам этого тестирования признать программу правильно работающей.
Входные данные
Входной файл INPUT.TXT содержит несколько наборов входных данных. Первая строка содержит t - число наборов входных данных. Оставшиеся строки входного файла содержат эти наборы.
Описание каждого набора начинается со строки, содержащей два целых числа n (1 ≤ n ≤ 50000) и m (1 ≤ m ≤ 100000) - количество компьютеров и отправленных писем соответственно. Далее следуют n строк, i-ая из которых содержит протокол работы почтового клиента на i-ом компьютере. Протокол работы состоит из целого числа ki(0 ≤ ki ≤ 2m) и ki чисел ai,j , описывающих события. Если ai,j > 0, то j-ым по счету событием на i-ом компьютере была посылка письма с идентификатором ai,j , если же ai,j < 0, то j-ым по счету событием на i-ом компьютере было получение письма с идентификатором -ai,j. Нулю ai,j равно быть не может.
Идентификатор письма - это целое число от 1 до 106. Внутри одного набора входных данных все письма имеют различные идентификаторы. Гарантируется, что все письма, которые были отправлены, были кем-то приняты, то есть сумма всех ki в одном наборе входных данных равна 2m.
Сумма чисел n по всем наборам входных данных не превосходит 50000, сумма чисел m по всем наборам входных данных не превосходит 100000.
Выходные данные
В выходной файл OUTPUT.TXT для каждого набора входных данных выведите ровно одну строку. Эта строка должна содержать слово YES, если программу можно считать правильно работающей по результатам тестирования, и NO - в противном случае.
Примеры
№
INPUT.TXT
OUTPUT.TXT
1
2
2 2
2 1 -2
2 2 -1
2 2
2 -2 1
2 -1 2
YES NO
2
1 2 3 2 1 -1
4 239 -239 366 -366
YES
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
