С того момента, как гигантские головы появились в небе, все человечество в опасности, поэтому все Рики и Морти из всех параллельных вселенных собираются в группы, чтобы найти решение, чтобы избавиться от гигантских голов.
Всего есть n параллельных вселенных, участвующих в этом событии (n Риков и n Морти). То есть в каждой из n вселенных есть один Рик и один Морти. Они собираются в m групп. Каждый человек может быть в нескольких группах, и каждая группа может содержать произвольное количество людей.
Рики и Морти зарегистрировались онлайн в этих группах. Также человек может вступить в группу больше одного раза (разработчик этого сайта не рассмотрел эту возможность).
Лето из вселенной #1 знает, что в каждой параллельной вселенной (включая это лето) ровно один из Рика и Морти из этой вселенной предатель и ровно один верен, но никто не знает кто именно. Лето знает, что мы обречены, если существует группа, в которой каждый участник предатель (они спланируют и уничтожат мир).
Лето знает, что если есть вероятность того, что миру конец (иначе говоря, есть группа, в которой все участники предатели), то оно должно немедленно отменить это событие. Поэтому оно хочет знать отменять ли событие. Вы должны ответить ему да только в том случае, если существует хотя бы один сценарий (из 2n возможных сценариев, 2 возможных сценария для того, кому быть предателем в каждой вселенной) такой, что миру наступит конец.
Первая строка входных данных содержит два целых числа n и m (1 ≤ n, m ≤ 104) — количество вселенных и количество групп соответственно.
Следующие m строк содержат информацию о группах. i-я из них сначала содержит целое число k (количество раз, которое кто-то вступил в i-ю группу, k > 0), за которым следует k целых чисел vi, 1, vi, 2, ..., vi, k. Если vi, j отрицательное, это значит, что Рик из вселенной номер - vi, j вступил в группу, иначе это значит, что Морти из вселеннй номер vi, j вступил в неё.
Сумма всех k по всем группам не превышает 104.
В единственной строке выведите ответ на вопрос Лета. Выведите «YES», если оно должно отменить событие, иначе «NO».
4 2
1 -3
4 -2 3 2 -3
YES
5 2
5 3 -2 1 -1 5
3 -5 2 5
NO
7 2
3 -1 6 7
7 -5 4 2 4 7 -3 4
YES
В первом тестовом примере 1-я группа содержит только Рика из вселенной номер 3, поэтому в случае, если он предатель, тогда все участники его группы предатели, и поэтому Лето должно отменить событие.
| Codeforces Round 406 (Div. 2) |
|---|
| Закончено |
