Музей#5733
Уявіть собі великий музей, наповнений розкішними залами та блискучими коридорами. Він настільки величезний, що планування будь-якої екскурсії в ньому стає справжнім викликом. Тут потрібна ваша допомога. Ви повинні допомогти в розробці системи знаків, які значно полегшать навігацію по всій будівлі. Ідея полягає в тому, що якщо в кімнаті є дверей, які ведуть через коридори до інших кімнат, ці двері та відповідні коридори (локально) позначаються номерами 1, 2, \ldots, d. Потім усім відвідувачам рекомендується дотримуватися простої процедури. Якщо вони знаходяться в кімнаті на самому початку своєї екскурсії, вони повинні вибрати двері з позначкою і пройти через відповідний коридор. Якщо вони знаходяться в кімнаті і увійшли в неї через двері з позначкою , вони повинні вибрати двері з наступним номером (тобто i+1, якщо i < d і , якщо i = d) і пройти через відповідний коридор. Ось простий приклад, у якому туристи починають у кімнаті і відвідують кімнати 1, 2, 3, 4, 5, 6 у такому порядку, проходячи через кожен коридор принаймні один раз:
Експонати в цьому музеї розміщені не лише в кімнатах, але й у коридорах, що з'єднують різні кімнати. Адже коридори чудово підходять для демонстрації картин і фотографій! Тому ми хочемо переконатися, що туристи, які дотримуються правил, пройдуть через кожен коридор принаймні один раз, за умови, що вони не швидко втомляться і будуть ходити досить довго, незалежно від того, з якої кімнати вони почали екскурсію. Ваше завдання - знайти таке маркування.
Виявляється, що з кожної кімнати виходить не більше коридорів, і весь музей з'єднаний, тобто можна пройти між будь-якими двома кімнатами, можливо, проходячи через інші кімнати по дорозі. Усі коридори, що виходять з однієї кімнати, ведуть до різних кімнат.
Містить кілька тестових випадків. Перший рядок містить кількість тестових випадків (t \le 100). Кожен тест починається з рядка, що містить кількість кімнат (3 \le n \le 10^5). Наступні рядків містять опис усіх коридорів. -й з них описує коридори, що з'єднують -ту кімнату з іншими. Він починається з цілого числа (1 \le d \le 3), кількості дверей у цій кімнаті. Далі йдуть цілих чисел r_1, r_2, \ldots, r_d, що дають номери кімнат, до яких ведуть ці двері (1 \le r_j \le n і r_j \ne r_k, якщо j \ne k і r_j \ne i). Усі коридори двосторонні, тому якщо є двері з кімнати до кімнати , то є двері з кімнати до кімнати . Загальний розмір вхідних даних не перевищуватиме МБ.
Для кожного тестового випадку виведіть рівно рядків. -й з них повинен містити номери кімнат, безпосередньо з'єднаних коридорами з кімнатою , у порядку їх призначених міток. Ви можете припустити, що завжди існує дійсне маркування дверей, вам просто потрібно знайти одне з них.
Приклад 1