Нове небо
Це — Output only задача. Тобто, вам потрібно відправити лише вихідний файл (не код). При відправці використовуйте компілятор "Plain Text". Вхідний тест доступний за посилання https://static.e-olymp.com/problems/10457/input.txt
Колонізація Марса – це вчорашній день. Треба думати далекоглядніше. Наприклад, які проблеми постануть перед колонізаторами за межами нашої галактики? Нова планета, нові континенти, нове зоряне небо.
Якщо з колонізацією континентів ми собі раду дамо: візьмемо якусь місцевість, назвемо Новою Новою Англією, побудуємо там Новий Новий Орлеан, - то з зоряним небом все непросто. Людство весь час жило тільки з одним небом, ну гаразд, якщо зважати на напівсфери, то з двома. І як, наприклад, орієнтуватися в чужому небі: де там Мала Ведмедиця, а де Південний Хрест, і чи є вони там взагалі, цього ніхто не знає.
Отже, шукатимемо в новому небі старі сузір’я.
Нехай зоряне небо представлене неорієнтованим графом. Зірки будуть вершинами, а уявні лінії які можуть формувати сузір’я, – ребрами. Нехай відомі сузір’я – це теж такі ж графи. Ми надаємо список сузір’їв і мапу неба, а ви знаходите ці сузір’я на мапі.
Кожна зірка та уявна лінія на небі може належати лише одному сузір’ю. Не всі шукані сузір’я присутні на небесній сфері. Зрештою, це ж інша галактика. При тому, деякі – можуть бути присутні декілька разів, у такому випадку знайти перше ліпше розташування буде достатньо.
Кількість отриманих балів у кожному тесті відповідає кількості успішно знайдених сузір’їв.
Input
Перший рядок містить одне ціле число T - кількість тестів.
Перший рядок кожного тесту містить єдине ціле число K. Далі слідує K+1 блоків, де перші K блоків описують шукані сузір’я, а останній – усю небесну мапу.
Кожен блок складається з двох рядків, у першому - два цілих числа: - кількість зірок у групі та – загальна кількість зв’язків між зірками поточної групи. Другий рядок містить пар цілих чисел, де кожна пара описує зв'язок між зірками поточної групи, нумерація зірок починається з нуля.
Output
Для кожного тесту потрібно вивести 1, якщо у вас є відповідь на це тест, або 0, якщо у вас немає відповіді.
Якщо у вас є відповідь, то вихідний файл повинен містити K рядків, де кожен рядок описує відповідне шукане сузір’я (у тому ж самому порядку що й у вхідних даних).
Рядок повинен містити -1 якщо сузір’я не знайдено, чи номерів зірок небесної сфери які утворюють поточне сузір’я. Зірки повинні бути перераховані у порядку що задовольняє початковий опис зв’язків шуканого сузір’я.
Examples
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