Забезпечення очищення#3573
Пам'ятаєте великий бій, коли Халк і Мерзота кидали один одного через будівлі Манхеттена? Або момент, коли Зелений Гоблін розбив Людиною-павуком півдюжини цегляних стін? Ці стіни мали розлетітися на мільйони шматків!
Добре, що у нас є супергерої, які можуть покарати лиходіїв, але чи замислювалися ви, хто займається відновленням завданої шкоди? Ви - президент корпорації з прибирання, і ваше завдання саме в цьому! Після великого бою вам слід зібрати всі шматки стін і скласти їх у тому порядку, в якому вони були до початку бою.
Малюнок 1: Стіна розбита на багато шматків
Стіна являє собою прямокутну ділянку, що розлітається на трикутні шматки, коли в неї кидають лиходія (див. Малюнок 1). Здійснивши складний візуальний аналіз, ви переконалися, з якої початкової структури був отриманий кожен маленький шматочок. По суті, у вас є план, який виглядає як на картинці вище. Крім того, ви помітили, що якщо два уламки знаходяться поруч, то вони йдуть по всій довжині розриву (ребра), що розділяє їх, як показано на Малюнку 2a.
Малюнок 2: Хороший, поганий і жахливий.
У вас є робот-збирач, який на місці допомагає відновити стіну. Робот може тільки опускати шматок, за один раз тільки один, зверху вниз. Робот не може переміщати шматок з одного місця на інше або обертати його. Необхідно бути обережним у складанні порядку команд, у якому робот буде збирати зламані шматки, щоб випадково не заблокувати місце, в яке слід опустити відповідний шматок (див. Малюнок 2d). Чи можете ви вказати порядок складання шматків, щоб повністю відновити стіну?
Перше число вказує на кількість стін, які вам слід відновити. Перше число для кожної стіни (2 \le n \le 1000000) вказує на кількість трикутних шматків, на які вона розбита. Далі слідують рядків, кожен з яких містить шість цілих чисел x_1, y_1, x_2, y_2, x_3, y_3 - декартові координати трьох вершин трикутника, що є шматком стіни. Перший рядок описує шматок , наступний шматок , і так далі. Три точки завжди задаються в порядку проти годинникової стрілки і завжди задають трикутник ненульової площі. Всі координати варіюються від до 10^9 включно, де позитивний напрямок осі вказує на напрямок "вгору". заданих шматків завжди і повністю покривають прямокутну область, без зазорів і перекриттів.
Для кожної стіни виведіть один рядок номерів шматків у тому порядку, в якому їх буде збирати робот для відновлення стіни. Якщо існує кілька таких послідовностей, то виведіть будь-яку з них.
Приклад 1