Нове небо

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

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

Якщо з колонізацією континентів ми собі раду дамо: візьмемо якусь місцевість, назвемо Новою Новою Англією, побудуємо там Новий Новий Орлеан, - то з зоряним небом все непросто. Людство весь час жило тільки з одним небом, ну гаразд, якщо зважати на напівсфери, то з двома. І як, наприклад, орієнтуватися в чужому небі: де там Мала Ведмедиця, а де Південний Хрест, і чи є вони там взагалі, цього ніхто не знає.

Отже, шукатимемо в новому небі старі сузір’я.

Нехай зоряне небо представлене неорієнтованим графом. Зірки будуть вершинами, а уявні лінії які можуть формувати сузір’я, – ребрами. Нехай відомі сузір’я – це теж такі ж графи. Ми надаємо список сузір’їв і мапу неба, а ви знаходите ці сузір’я на мапі.

Кожна зірка та уявна лінія на небі може належати лише одному сузір’ю. Не всі шукані сузір’я присутні на небесній сфері. Зрештою, це ж інша галактика. При тому, деякі – можуть бути присутні декілька разів, у такому випадку знайти перше ліпше розташування буде достатньо.

Кількість отриманих балів у кожному тесті відповідає кількості успішно знайдених сузір’їв.

Вхідні дані

Перший рядок містить одне ціле число T - кількість тестів.

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

Кожен блок складається з двох рядків, у першому - два цілих числа: $N_i$ - кількість зірок у групі та $M_{і}$ – загальна кількість зв’язків між зірками поточної групи. Другий рядок містить $M_{і}$ пар цілих чисел, де кожна пара описує зв'язок між зірками поточної групи, нумерація зірок починається з нуля.

Вихідні дані

Для кожного тесту потрібно вивести 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