e-olymp
Problems

Нове небо

Нове небо

Це~--- \textbf{Output only} задача. Тобто, вам потрібно відправити лише вихідний файл (не код). При відправці використовуйте компілятор "Plain Text". Вхідний тест доступний за посилання \url{https://static.e-olymp.com/problems/10457/input.txt} Колонізація Марса – це вчорашній день. Треба думати далекоглядніше. Наприклад, які проблеми постануть перед колонізаторами за межами нашої галактики? Нова планета, нові континенти, нове зоряне небо. Якщо з колонізацією континентів ми собі раду дамо: візьмемо якусь місцевість, назвемо Новою Новою Англією, побудуємо там Новий Новий Орлеан, - то з зоряним небом все непросто. Людство весь час жило тільки з одним небом, ну гаразд, якщо зважати на напівсфери, то з двома. І як, наприклад, орієнтуватися в чужому небі: де там Мала Ведмедиця, а де Південний Хрест, і чи є вони там взагалі, цього ніхто не знає. Отже, шукатимемо в новому небі старі сузір’я. Нехай зоряне небо представлене неорієнтованим графом. \textit{Зірки будуть вершинами}, а \textit{уявні лінії які можуть формувати сузір’я,} – \textit{ребрами}. Нехай відомі сузір’я – це теж такі ж графи. Ми надаємо список сузір’їв і мапу неба, а ви знаходите ці сузір’я на мапі. Кожна зірка та уявна лінія на небі може належати лише одному сузір’ю. Не всі шукані сузір’я присутні на небесній сфері. Зрештою, це ж інша галактика. При тому, деякі – можуть бути присутні декілька разів, у такому випадку знайти перше ліпше розташування буде достатньо. Кількість отриманих балів у кожному тесті відповідає кількості успішно знайдених сузір’їв. \InputFile Перший рядок містить одне ціле число T - кількість тестів. Перший рядок кожного тесту містить єдине ціле число K. Далі слідує K+1 блоків, де перші K блоків описують шукані сузір’я, а останній – усю небесну мапу. Кожен блок складається з двох рядків, у першому - два цілих числа: $N_i$ - кількість зірок у групі та $M_і$ – загальна кількість зв’язків між зірками поточної групи. Другий рядок містить $M_і$ пар цілих чисел, де кожна пара описує зв'язок між зірками поточної групи, нумерація зірок починається з нуля. \OutputFile Для кожного тесту потрібно вивести 1, якщо у вас є відповідь на це тест, або 0, якщо у вас немає відповіді. Якщо у вас є відповідь, то вихідний файл повинен містити K рядків, де кожен рядок описує відповідне шукане сузір’я (у тому ж самому порядку що й у вхідних даних). Рядок повинен містити -1 якщо сузір’я не знайдено, чи $N_i$ номерів зірок небесної сфери які утворюють поточне сузір’я. Зірки повинні бути перераховані у порядку що задовольняє початковий опис зв’язків шуканого сузір’я. \Example \begin{example} \exmp{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 } \end{example}
Time limit 0.1 seconds
Memory limit 256 MiB