Новое небо

Це — Output only задача. Это значит, что вам нужно отправить только выходной файл (не код). При отправке используйте компилятор "Plain Text". Входной тест доступен по ссылке https://static.e-olymp.com/problems/10457/input.txt

Колонизация Марса уже в прошлом. Нужно смотреть дальше. Например, какие проблемы могут возникнуть у колонизаторов за пределами нашей галактики? Новая планета, новые континенты, новое звездное небо.

Если с колонизацией континентов мы справимся: выберем какую-то местность, назовем её Новой Новой Англией, построим там Новый Новый Орлеан, - то со звездным небом всё не так просто. Человечество всегда жило под одним небом, ну ладно, если учитывать полусферы, то под двумя. И как, например, ориентироваться в чужом небе: где там Малая Медведица, а где Южный Крест, и есть ли они там вообще, этого никто не знает.

Итак, будем искать в новом небе старые созвездия.

Пусть звездное небо представлено неориентированным графом. Звезды будут вершинами, а воображаемые линии, которые могут формировать созвездия, – ребрами. Пусть известные созвездия – это тоже такие же графы. Мы предоставляем список созвездий и карту неба, а вы находите эти созвездия на карте.

Каждая звезда и воображаемая линия на небе может принадлежать только одному созвездию. Не все искомые созвездия присутствуют на небесной сфере. В конце концов, это же другая галактика. При этом, некоторые могут присутствовать несколько раз, в таком случае достаточно найти первое попавшееся расположение.

Количество полученных баллов в каждом тесте соответствует количеству успешно найденных созвездий.

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

Первая строка содержит одно целое число T - количество тестов.

Первая строка каждого теста содержит единственное целое число K. Далее следует K+1 блоков, где первые K блоков описывают искомые созвездия, а последний – всю небесную карту.

Каждый блок состоит из двух строк, в первой - два целых числа: $N_i$ - количество звезд в группе и $M_i$ – общее количество связей между звездами текущей группы. Вторая строка содержит $M_i$ пар целых чисел, где каждая пара описывает связь между звездами текущей группы, нумерация звезд начинается с нуля.

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

Для каждого теста нужно вывести 1, если у вас есть ответ на этот тест, или 0, если у вас нет ответа.

Если у вас есть ответ, то выходной файл должен содержать K строк, где каждая строка описывает соответствующее искомое созвездие (в том же самом порядке, что и во входных данных).

Строка должна содержать -1, если созвездие не найдено, или $N_i$ номеров звезд небесной сферы, которые образуют текущее созвездие. Звезды должны быть перечислены в порядке, который удовлетворяет начальное описание связей искомого созвездия.

Примеры

1
3
4 4
0 1 1 2 2 3 3 0
3 3 
0 1 1 2 2 0
4 3
0 1 0 2 0 3
7 7
0 1 1 4 1 2 2 3 3 5 3 6 5 6

1
-1
3 5 6
1 0 2 4