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

Школьник Миша устал заниматься спортивным программированием, и поэтому решил все бросить и уйти в магический лес торговать магическими яблоками.

Его друг Даня пришел в этот магический лес, чтобы навестить Мишу. Какого же было его удивление, когда он узнал, что Миша нашел там много друзей, таких же бывших спортивных программистов. И у всех них, как и у Миши, есть своя лавка, где они продают магические яблоки. Чтобы поддержать друзей, так кардинально поменявших свою жизнь, он решил скупить у них весь ассортимент.

Процесс покупки устроен следующим образом: всего есть $$$n$$$ лавок, пронумерованных целыми числами от $$$1$$$ до $$$n$$$, и $$$m$$$ видов магических яблок, пронумерованных целыми числами от $$$1$$$ до $$$m$$$. В каждой лавке продается какое-то множество видов яблок. Даня посещает все лавки в порядке возрастания номера, начиная с первой. Заходя в лавку он покупает по одному магическому яблоку каждого вида, который в этой лавке продается, и кладет их к себе в рюкзак.

Однако, магические яблоки не были бы магическими, если бы с ними было все в порядке. Дело в том, что когда два яблока одного типа оказываются вместе в рюкзаке, все яблоки в нем магическим образом исчезают. Важно, что исчезновение происходит уже после того, как Даня положил яблоки в рюкзак и покинул лавку.

Вернувшись домой, Даня понял, что где-то в лесу он успел потерять свой рюкзак. Помня для некоторых лавок, какие виды магических яблок в них продавались, он хочет узнать, какое максимальное количество яблок могло оказаться у него в рюкзаке после всех покупок в лучшем случае.

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

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

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

Каждая из следующих $$$n$$$ строк описывает ассортимент очередного прилавка в формате, описанном ниже.

Каждая строка начинается с целого числа $$$k_i$$$ ($$$0 \le k_i \le 2 \cdot 10^5$$$). За ней следуют $$$k_i$$$ различных целых чисел $$$a_{ij}$$$ ($$$1 \le a_{ij} \le m$$$) — виды яблок, продаваемых в $$$i$$$-й лавке. Если $$$k_i = 0$$$, то Даня не помнит какой ассортимент был в этой лавке, и множество видов яблок может быть каким угодно (в том числе и пустым).

Гарантируется, по что сумма всех $$$k_i$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$ и сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

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

Для каждого набора данных выведите одно целое число — максимальное количество яблок, которое могло оказаться в рюкзаке Дани после посещения всех лавок в лучшем случае.

Пример
Входные данные
4
3 4
2 1 2
2 4 1
2 1 2
4 4
2 1 2
2 3 4
0
1 1
2 5
0
0
5 3
0
3 1 2 3
2 3 1
0
1 3
Выходные данные
2
1
5
3
Примечание

В первом наборе входных данных Даня помнит про все лавки, поэтому процесс будет детерминированным. В первой лавке он возьмет два яблока, и еще два во второй, но после того как он положит их в рюкзак, они исчезнут. Поэтому в конце останется только $$$2$$$ яблока, которые он возьмет в третьей лавке.

Во втором наборе входных данных, если в третьей лавке будет пусто, то после посещения четвертой лавки все яблоки исчезнут. В любом другом случае яблоки исчезнут после третьей лавки, и в четвертой Даня сможет взять одно яблоко, поэтому ответ $$$1$$$.

В третьем наборе входных данных, в первой лавке могут продаваться все виды яблок, а во второй лавке может ничего не продаваться. Тогда в конце останутся все $$$5$$$ яблок.