eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Hовини

Hовини

Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB

У місті введено рух автобусів. Усі автобуси мають циклічні маршрути. Деякі маршрути мають спільні зупинки. Коли два чи більше автобусів зустрічаються на одній зупинці, водії обмінюються усіма новинами, які їм відомі на даний момент (після того як вони відїдуть від зупинки, усі будуть знати однакові новини).

Водії починають рух своїх автобусів одночасно, і у цей час кожен з водіїв знає одну новину, яку не знає жоден з інших.

Рух автобусів синхронізовано у тому смислі, що час, необхідний для переїзду від однієї зупинки до наступної, однаковий для усіх автобусів.

Існує D водіїв (і, відповідно, D автобусів), яких пронумеровано від 1 до D, та S зупинок, які мають номери від 1 до S.

Написати програму BUS, яка визначить, чи може кожен водій знати усі новин своїх колег, якщо тривалісь знаходження на маршруті необмежена.

Вхідні дані

Вхідний файл у першому рядку містить число тестів N. Далі йде N блоків інформації, кожен з яких відповідає одному тесту. Перший рядок блоку містить два цілих числа D (1D100) та S (1S250). Кожен з наступних D рядків описує маршрут одного з автобусів таким чином: перше число — кількість зупинок на даному маршруті M_i, після чого M_i різних цілих чисел, які задають послідовність зупинок маршрута. Рух автобуса починається з зупинки, яка вказана першою.

Вихідні дані

Кожен рядок вихідного файлу повинен містити відповідь для одного тесту. Необхідно вивести 1, якщо кожен водій взнає усі новини, або 0 у протилежному виппадку.

Приклад

Вхідні дані #1
2
1 3
3 1 2 3
2 2
2 1 2
2 2 1
Вихідні дані #1
1
0