B. Слияние множеств
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам даны $$$n$$$ множеств $$$S_1,S_2,\ldots,S_n$$$, где каждый элемент множества — это целое число от $$$1$$$ до $$$m$$$.

Вы хотите выбрать некоторые из множеств (возможно, ни одно или все), так чтобы каждое целое число от $$$1$$$ до $$$m$$$ было включено в по крайней мере одно из выбранных множеств.

Вам нужно определить, существуют ли по крайней мере три способа выбрать множества.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$m$$$ ($$$2 \leq n \leq 5\cdot 10^4$$$, $$$1\le m \leq 10^5$$$) — количество множеств и верхняя граница целых чисел в множествах.

Затем следуют $$$n$$$ строк, в $$$i$$$-й строке сначала содержится целое число $$$l_i$$$ ($$$1\le l_i\le m$$$) — размер множества $$$S_i$$$.

Затем следуют $$$l_i$$$ целых чисел $$$S_{i,1}, S_{i,2}, \ldots, S_{i, l_i}$$$ в той же строке ($$$1\le S_{i,1} \lt S_{i,2} \lt \cdots \lt S_{i, l_i}\le m$$$) — элементы множества $$$S_i$$$.

Обозначим $$$L=\sum\limits_{i=1}^n l_i$$$. Гарантируется, что:

  • Сумма $$$n$$$ по всем наборам входных данных не превосходит $$$5\cdot 10^4$$$;
  • Сумма $$$m$$$ по всем наборам входных данных не превосходит $$$10^5$$$;
  • Сумма $$$L$$$ по всем наборам входных данных не превосходит $$$2\cdot 10^5$$$.
Выходные данные

Для каждого набора входных данных выведите «YES», если существуют по крайней мере три способа выбрать множества. В противном случае выведите «NO».

Вы можете выводить каждую букву в любом регистре (строчную или заглавную). Например, строки «yEs», «yes», «Yes», и «YES» будут распознаны как положительные ответы.

Пример
Входные данные
6
3 2
2 1 2
1 1
1 2
4 10
3 1 2 3
2 4 5
1 6
4 7 8 9 10
2 5
4 1 2 3 4
4 1 2 3 4
5 5
5 1 2 3 4 5
5 1 2 3 4 5
5 1 2 3 4 5
5 1 2 3 4 5
5 1 2 3 4 5
5 10
4 1 2 3 4
5 1 2 5 6 7
5 2 6 7 8 9
4 6 7 8 9
2 9 10
5 5
1 1
1 2
1 3
2 4 5
1 5
Выходные данные
YES
NO
NO
YES
YES
NO
Примечание

В первом наборе входных данных существует $$$5\ge 3$$$ возможных способов выбрать множества:

  • $$$S_1$$$ — оба числа $$$1$$$ и $$$2$$$ включены в $$$S_1$$$;
  • $$$S_1$$$ и $$$S_2$$$ — $$$1$$$ включено в $$$S_1$$$ и $$$S_2$$$, а $$$2$$$ включено в $$$S_1$$$;
  • $$$S_1$$$ и $$$S_3$$$ — $$$1$$$ включено в $$$S_1$$$, а $$$2$$$ включено в $$$S_1$$$ и $$$S_3$$$;
  • $$$S_2$$$ и $$$S_3$$$ — $$$1$$$ включено в $$$S_2$$$, а $$$2$$$ включено в $$$S_3$$$;
  • $$$S_1$$$, $$$S_2$$$ и $$$S_3$$$ — $$$1$$$ включено в $$$S_1$$$ и $$$S_2$$$, а $$$2$$$ включено в $$$S_1$$$ и $$$S_3$$$.

Обратите внимание, что выбирать только $$$S_2$$$ недопустимо, так как $$$2$$$ не включено в $$$S_2$$$.

Во втором наборе входных данных единственный способ — выбрать все множества.

В третьем наборе входных данных число $$$5$$$ не встречается ни в одном из множеств, поэтому нет способа выбрать множества.

В четвертом наборе входных данных выбор любого непустого набора множеств допустим, поэтому количество способов равно $$$2^5-1=31\ge3$$$.