Алгоритмы на графах

В операционной системе Xunil информация обо всех файлах и директориях хранится в специальном файле в следующем формате:

emoh

 vonavi

  a.doc

  b.doc

 vortep

  .bashrc

 vorodis

  onrop

   1.avi

   2.avi

rav

 bil

 

Имена файлов, и только они, содержат точку.

Требуется по данному имени файла найти путь к нему. Если таких файлов несколько, вывести путь к файлу, который записан выше.

Входные данные
В первой строке вводится имя искомого файла. Во второй строке вводится общее количество файлов и директорий. В остальных строках вводится информация о файлах и директориях в указанном выше формате (директория или файл, находящиеся внутри другой директории, отделяются одним дополнительным пробелом в начале строки). Количество строк в файле и количество символов в каждой строке не превосходит 100.

Выходные данные
Выведите путь к файлу в формате /директория/директория/…/файл

Гарантируется, что такой файл есть.

Гарантируется, что длина строки ответа не превосходит 255.

В этой задаче Вам вновь придется помочь Берляндии. Эта страна состоит из n городов, некоторые пары из которых соединены двусторонними дорогами, каждая дорога характеризуется своей длиной. Все города пронумерованы числами от 1 до n, столица имеет номер 1. Время от време ни Президент объезжает страну, посещая города страны. Целью каждой поездки является один из городов, к которому он едет из столицы вдоль дорог одним из кратчайших путей.

В далекие времена (когда задачи на алгоритм Дейкстры вызывали сложность) специальное ведомство составила такой набор дорог T, вдоль которого можно было проехать из столицы в любой город, причем единственным образом. Разумеется, путь по дорогам из набора T из столицы в каждый город являлся кратчайшим. Особо умные жители страны попросту называли этот набор дорог "деревом кратчайших путей". Известно, что Президент пользовался дорогами из T во время своих поездок. За прошедшие годы этот набор перестал быть секретным, и, поэтому, стал объектом повышенного внимания берляндских экстремистов. У специального ведомства новое задание. Для каждого города кроме столицы необходимо вычислить кратчайшее расстояние до него, при условии, что та дорога по которой Президент должен был закончить свой путь в этот город является атакованной и проезжать по ней нельзя.

Входные данные
В первой строке входного файла записана пара целых чисел n и m (2 ≤ n≤ 4000; n−1 ≤ m ≤100000), где n — количество городов в стране, а m— количество дорог в этой стране. Далее в m строках содержатся описания дорог, по одной дороге в строке. Каждая дорога задается четверкой целых чисел a_j, b_j, l_j, t_j , где a_j, b_j это номера городов, соединяемых дорогой (1 ≤ a_j,b_j ≤ n; a_j≠b_j), l_j — ее длина (1 ≤ l_j≤ 10⁵), а t_j равно 1 если дорога принадлежит дереву кратчайших путей и 0 в противном случае.

Гарантируется, что набор T удовлетворяет описанным выше свойствам. Между парой городов может быть более одной дороги. Все дороги двусторонние.

Выходные данные
Выведите n−1 число в строку через пробелы. i-ое число должно быть равно либо длине кратчайшго пути из столицы в город i+1, при условии, что по той дороге из T, которой Президент заканчивал свой путь в этот город, передвигаться нельзя, либо -1, если добраться до города i+1 вообще невозможно.

Город Восточный постоянно страдает от недостатка воды. Для устранения этой проблемы была построена новая водопроводная труба. Строительство трубы началось с обоих концов одновременно, и спустя некоторое время половины соединились. Ну, почти. Первая половина трубы заканчивалась в точке (x₁, y₁), а вторая - в точке (x₂, y₂).

К сожалению, осталось лишь несколько отрезков трубы различной длины. Более того, из-за специфики местной технологии трубы могут быть проложены только в направлении с севера на юг или с востока на запад и соединяются, образуя или прямую, или угол 90 градусов. Требуется, зная длины отрезков труб L₁, L₂, ..., L_K и количество отрезков каждой длины C₁, C₂, ..., C_K, сконструировать трубу, соединяющую две заданные точки, или определить, что это невозможно.

Ограничения: 1 <= K <= 4, 1 <= x₁, y₁, x₂, y₂, L_i <= 1000, 1 <= C_i <= 10, все числа целые.



Входные данные
В первой строке находятся числа x₁, y₁, x₂, y₂, K, затем 2_K чисел: L₁, L₂, ..., L_K, C₁, C₂, ..., C_K.

Выходные данные
Вывести одно число - минимальное количество нужных отрезков труб или -1, если соединение невозможно.

На столе лежат несколько кусков ткани, не перекрывая друг друга. Эти куски могут иметь дыры, в том числе и настолько большие, что в них может поместиться целый кусок ткани. Был получен чёрно-белый образ поверхности стола, на котором области, покрытые тканью, представлены символами *, а свободные площади - точками. Один кусок ткани, таким образом, представлен 4-связной областью символов *, то есть группой *, соседствующих друг с другом горизонтально или вертикально, но не по диагонали.

.***..***
.*.*.**.*
.***.*.**
*...**.*.

На схеме три куска - один без дыр, а два - с одной дырой каждый: первый площадью 8, второй - площадью 12.
Ваша цель - найти кусок с наибольшим количеством дыр в нём. Дыра - это 4-связная область точек, полностью окружённых символами *. Если несколько кусков имеют одинаковое количество дыр, нужно выбрать кусок минимальной площади.

Входные данные
В первой строке содержатся два числа W и H, разделённые пробелами. Следующие H строк содержат по W символов каждая. Символы в этих строках - или * (ASCII 42), или точка (ASCII 46).

Ограничения: 1 <= W, H <= 100.

Выходные данные
Вывести одно целое число - площадь минимального из наиболее дырявых кусков. Если нет кусков с дырами, выходной файл должен содержать ноль.

Пещера представлена кубом, разбитым на N частей по каждому измерению (то есть на N 3 кубических клеток). Каждая клетка может быть или пустой, или полностью заполненной камнем. Исходя из положения спелеолога в пещере, требуется найти, какое минимальное количество перемещений по клеткам ему требуется, чтобы выбраться на поверхность. Переходить из клетки в клетку можно, только если они обе свободны и имеют общую грань.

Ограничения: 1 <= N <= 30.

Входные данные
В первой строке содержится число N. Далее следует N блоков. Блок состоит из пустой строки и N строк по N символов: # - обозначает клетку, заполненную камнями, точка - свободную клетку. Начальное положение спелеолога обозначено заглавной буквой S. Первый блок представляет верхний уровень пещеры, достижение любой свободной его клетки означает выход на поверхность. Выход на поверхность всегда возможен.

Выходные данные
Вывести одно число - длину пути до поверхности.

Дано N прямоугольников со сторонами, параллельными осям координат. Требуется определить, на сколько частей эти прямоугольники разбивают плоскость (внутри частей не должно быть границ прямоугольников).

Входные данные
В первой строке содержится число прямоугольников N. Далее идут N строк, содержащих по 4 числа x₁, y₁, x₂, y₂ - координаты двух противоположных углов прямоугольника.

Ограничения: 1 <= N <= 100, координаты представляют собой целые числа и по абсолютной величине не превосходят 10 000.

Выходные данные
Вывести одно число - количество частей, на которые разбивается плоскость.

Дана шахматная доска, состоящая из N*N клеток, несколько из них вырезано. Провести ходом коня через невырезанные клетки путь минимальной длины из одной заданной клетки в другую.

Входные данные
В первой строке задано число N. В следующих N строках содержится по N символов. Символом # обозначена вырезанная клетка, точкой - невырезанная клетка, @ - заданные клетки (таких символов два). 2 <= N <= 50.

Выходные данные
Если путь построить невозможно, вывести "Impossible", в противном случае вывести такую же карту, как и на входе, но пометить все промежуточные положения коня символом @.

В таблице из N строк и N столбцов некоторые клетки заняты шариками, другие свободны. Выбран шарик, который нужно переместить, и место, куда его нужно переместить. Выбранный шарик за один шаг перемещается в соседнюю по горизонтали или вертикали свободную клетку. Требуется выяснить, возможно ли переместить шарик из начальной клетки в заданную, и если возможно, то найти путь из наименьшего количества шагов.

Входные данные
В первой строке находится число N, в следующих N строках - по N символов. Символом точки обозначена свободная клетка, латинской заглавной O - шарик, @ - исходное положение шарика, который должен двигаться, латинской заглавной X - конечное положение шарика. 2 <= N <= 250.

Выходные данные
В первой строке выводится Y, если движение возможно, или N, если нет. Если движение возможно, далее следует N строк по N символов - как и на вводе, но X, а также все точки по пути заменяются плюсами +.

Лабиринт представляет собой квадрат, состоящий из NxN сегментов. Каждый из сегментов может быть либо пустым, либо заполненным монолитной каменной стеной. Гарантируется, что левый верхний и правый нижний сегменты пусты. Лабиринт обнесён сверху, снизу, слева и справа стенами, оставляющими свободными только левый верхний и правый нижний углы. Директор лабиринта решил покрасить стены лабиринта, видимые изнутри (см. рисунок). Помогите ему рассчитать количество краски, необходимой для этого.



Входные данные
В первой строке находится число N, затем идут N строк по N символов: точка обозначает пустой сегмент, решётка - сегмент со стеной. 3 <= N <= 33, размер сегмента 3 x 3 м, высота стен 3 м.

Выходные данные
Вывести одно число - площадь видимой части внутренних стен лабиринта в квадратных метрах.

В таблице из N строк и N столбцов некоторые клетки заняты шариками, другие свободны. Выбран шарик, который нужно переместить, и место, куда его нужно переместить. Выбранный шарик за один шаг перемещается в соседнюю по горизонтали или вертикали свободную клетку. Требуется выяснить, возможно ли переместить шарик из начальной клетки в заданную, и, если возможно, то найти путь из наименьшего количества шагов.

Входные данные
В первой строке находится число N, в следующих N строках - по N символов. Символом точки обозначена свободная клетка, латинской заглавной O - шарик, @ - исходное положение шарика, который должен двигаться, латинской заглавной X - конечное положение шарика. 2 <= N <= 40.

Выходные данные
В первой строке выводится Y, если движение возможно, или N, если нет. Если движение возможно, далее следует N строк по N символов - как и на вводе, но буква X, а также все точки по пути заменяются плюсами.

Дан неориентированный граф без кратных ребер и петель. В нем уже содержится некоторое (возможно, нулевое) количество ребер. Можно за определенную плату добавлять в него новые ребра (плата своя для каждого ребра). Требуется за наименьшую плату сделать граф связным.

Входные данные
В первой строке входных данных содержится одно целое число N (1 ≤ N ≤ 50) – количество вершин в исходном графе. Далее в N строках записано по N неотрицательных целых чисел в каждой ( j -е число в i -й строке соответствует стоимости добавления ребра, соединяющего вершины i и j, 0 соответствует уже существующему ребру, положительное число – несуществующему), числа не превышают 100. Матрица симметрична.

Выходные данные
Вывести единственное число – минимально возможную стоимость дополнения данного графа до связного.

Даны несколько точек на плоскости, некоторые из которых соединены отрезками. Множество точек называется связанным, если из любой его точки можно перейти в любую точку, перемещаясь только по отрезкам (переходить с отрезка на отрезок возможно только в точках исходного множества). Можно за определенную плату добавлять новые отрезки (стоимость добавления равна длине добавляемого отрезка). Требуется за минимальную стоимость сделать данное множество связанным.

Входные данные
В первой строке входных данных содержится одно целое число N
 (1 ≤ N ≤ 50) – количество точек. Далее в N строках записано по 2 натуральных числа – координаты точек (координаты не превышают 100). Все точки различны. Далее дано число M – количество уже существующих отрезков. В следующих M строках записаны по 2 числа – номера начала и конца соответствующего отрезка.

Выходные данные
Вывести единственное число – минимально возможную стоимость дополнения с точностью 5 знаков после запятой.

Дан неориентированный граф без кратных ребер и петель. В нем уже содержится некоторое (возможно, нулевое) количество ребер. Можно за определенную плату добавлять в него новые ребра (плата своя для каждого ребра). Требуется за наименьшую плату сделать граф связным.

Входные данные
В первой строке входных данных содержится одно целое число N (1 ≤ N ≤ 50) – количество вершин в исходном графе. Далее в N строках записано по N положительных целых чисел в каждой ( j -е число в i -й строке соответствует стоимости добавления ребра, соединяющего вершины i и j ), числа не превышают 100. В следующих N строках записаны по N чисел, каждое из которых является единицей или нулем (1, если вершины соединены, и 0, если не соединены). Обе матрицы симметричны.

Выходные данные
Вывести единственное число – минимально возможную стоимость дополнения данного графа до связного.

На полигоне, на котором проводятся военные учения сухопутных войск Флатландии, вырыты n окопов. Каждый окоп вырыт вдоль границы прямоугольника со сторонами, параллельными направлениям север–юг и запад–восток. При этом окопы могут иметь общие точки, но никакие два окопа не имеют общего участка ненулевой длины.

Очередные учения должны продемонстрировать способность солдат быстро и незаметно перемещаться из точки A в точку B.

Во время учений солдаты могут перемещаться либо по окопам, либо по траншеям, которые они могут прокапывать между окопами. При этом по окопам и выкопанным траншеям солдат может бегать настолько быстро, что временем перемещения от одной точки до другой можно пренебречь (будем считать его равным нулю). Траншеи же солдат копает со скоростью 1 метр в час.

Заданы точки A и B. Требуется определить, за какое минимальное время солдат во время учений сможет переместиться из А в B. Шириной траншей и окопов можно пренебречь.

Формат входных данных

Первая строка содержит число n — количество окопов на полигоне (1 ≤ n ≤ 500). Введем систему координат на полигоне таким образом, чтобы ось OX была ориентирована с запада на восток, а ось OY — с юга на север. Следующие n строк описывают окопы, каждый окоп описывается четырьмя целыми числами x₁, y₁, x₂, y₂ — координатами юго-западного и северо-восточного углов, соответственно (–10⁴ ≤ x₁ < x₁ ≤ 10⁴, –10⁴ ≤ y₁ < y₂ ≤ 10⁴).

Последние две строки содержат по два целых числа: x_A, y_A — координаты точки A и x_B, y_B — координаты точки B, соответственно (–10⁴ ≤ x_A, y_A, x_B, y_B ≤ 10⁴). Гарантируется, что точки A и B находятся в окопах. Все координаты заданы в метрах.

Формат выходных данных

Выведите одно вещественное число — количество часов, которое потребуется солдату, чтобы добраться из точки A до точки B. Ответ должен отличаться от правильного не более чем на 10^-6.

Рассмотрим таблицу, состоящую из N строк и M столбцов. Если в каждой ячейке такой таблицы стоит целое число, назовем такую таблицу целочисленной матрицей. Скажем, что эта матрица кратна чиcлу p, если все числа в ее ячейках кратны p.

Рассмотрим теперь суммы элементов матрицы по строкам и столбцам соответственно. Обозначим сумму чисел i-й строки за Hi, а сумму чисел j-го столбца за Vj. Упорядоченный набор чисел (H₁, H₂, …, H_N, V₁, V₂, …, V_M) назовем профилем матрицы. Скажем, что матрица почти кратна p, если все числа, входящие в ее профиль, кратны p. Почти кратная 5 матрица и ее профиль изображены на рисунке 1.


Если две матрицы A и B имеют одинаковый размер, причем элемент, стоящий на пересечении i-й строки и j
-го столбца в матрице A отличается от соответствующего элемента матрицы B не более чем на p, скажем, что A отличается от B не более чем на p. Скажем, что матрица B похожа на матрицу A относительно числа p, если

1. отличается от не более чем на p
2. профили B и A совпадают.

На рисунке 2 изображены две похожие относительно числа 5 матрицы, первая из них почти кратна 5, а вторая кратна 5. Третья матрица на рисунке 2 тоже кратна 5, но непохожа на первую (хотя похожа на вторую).

Дано число p и почти кратная p матрица A. Ваша задача - найти такую матрицу B, чтобы она была кратна p и похожа на A относительно p.

Входные данные
В первой строке входных данных задаются целые числа p (1 <= p <= 10), N и M (1 <= N, M <= 30). Следующие N строк содержат по M целых неотрицательных чисел, не превышающих 1000, которые являются элементами исходной матрицы A.

Выходные данные
Выведите матрицу B по строкам - сначала M элементов первой строки, затем M элементов второй, и т. д. Разделяйте числа пробелами и/или переводами строк. Заботиться о красивом форматировании таблицы не надо. Если искомой матрицы не существует, выведите единственное число - "-1". Если решений несколько, выведите любое из них.

Андрюше на день рождения подарили хомячка. Пока Андрюша не купил для него клетку, он решил сделать ему клетку из подручных средств. Для изготовления клетки он решил использовать набор кубиков, подаренный ему на прошлый день рождения. Однако, неожиданно выяснилось, что сестра Андрюши склеила кубики суперклеем, и отделить их друг от друга не представляется возможным.

Все кубики оказались склеены в две фигуры. Любые два кубика в каждой из фигур либо не имеют общих точек, либо имеют общую грань, либо имеют общее ребро, но в последнем случае есть кубик, с которым каждый из них имеет общую грань. Каждую фигуру можно положить на стол так, что каждый кубик будет касаться стола одной из своих граней.

Теперь Андрюша хочет положить эти две фигуры на стол так, чтобы получилась клетка для хомячка. Фигуры должны быть положены таким образом, чтобы каждый кубик касался стола гранью. Стороны нижних граней кубиков должны быть параллельны сторонам стола. Любые два кубика, принадлежащие различным фигурам, должны либо не касаться друг друга, либо иметь общую грань, либо иметь общее ребро. Фигуры разрешается поворачивать и переворачивать.


Положив фигуры, Андрюша собирается выпустить хомячка на стол. Чтобы он не упал со стола, у него не должно быть возможности добраться от точки, в которую Андрюша его выпустит, до края стола. Хомячок не может перелезать через кубики, и, в частности, не может пролезть между двумя кубиками, имеющими общее ребро. Стол существенно больше каждой из фигур.

Андрюша хочет, чтобы площадь, по которой может бегать хомячок, была как можно больше. Помогите ему выяснить, какая максимальная площадь может быть у территории, до которой сможет добраться хомячок. Площадь грани кубика будем считать равной единице.

Например, две фигуры, показанные на рисунке выше, можно расположить как показано на следующем рисунке. Если выпустить хомячка в точку, отмеченную стрелкой, то доступная ему территория будет иметь площадь, равную четырем.

Входные данные
В первой строке вводятся два числа: h₁ и w₁ (1 <= h₁, w₁ <= 10). Следующие h₁
строк содержат по w₁ символов и описывают первую фигуру, вид сверху. Каждый из этих символов - либо "*" (звездочка), либо "." (точка), звездочка обозначает кубик, а точка – пустое место.

Далее в отдельной строке вводятся два числа: h₂ и w₂  (1 <= h₂,  w₂ <= 10). Следующие h₂ строк содержат по w₂ символов и описывают вторую фигуру в формате, аналогичном формату первой. Каждая из фигур связна и содержит хотя бы один кубик.

Выходные данные
Выведите одно число – максимальную площадь, которая может быть доступна хомячку. Если сделать клетку для хомячка невозможно, выведите 0.

Государство Флатландия представляет собой прямоугольник размером M × N, состоящий из единичных квадратиков. Флатландия разделена на K провинций (2 <= K <= 100). Каждая провинция представляет собой связное множество квадратиков, т.е. из каждой точки провинции можно дойти до любой другой ее точки, при этом разрешается переходить с квадратика на квадратик, только если они имеют общую сторону (общей вершины недостаточно). Во Флатландии нет точки, которая граничила бы более чем с тремя провинциями (т.е. четыре квадратика, имеющие общую вершину, не могут принадлежать четырем разным провинциям).

Каждая провинция имеет свой символ. Столица Флатландии находится в провинции, которой принадлежит символ A (заглавная латинская буква A). Провинция называется пограничной, если она содержит граничные квадратики. Провинция, в которой находится столица Флатландии, не является пограничной.

Король соседнего с Флатландией королевства Ректилания решил завоевать Флатландию. Для этого он хочет захватить столицу Флатландии. Однако он знает, что сил его армии недостаточно, чтобы сделать это сразу. Поэтому сначала он хочет окружить столичную провинцию, чтобы ослабить силы противника долгой блокадой, а потом захватить столицу.

Чтобы окружить провинцию, требуется захватить все провинции, с которыми она граничит. Две провинции граничат, если существует два квадратика, имеющие общую сторону, один из которых принадлежит первой из них, а другой - второй. Чтобы захватить провинцию, надо чтобы выполнялось одно из двух условий: либо она пограничная, либо граничит с какой-либо уже захваченной провинцией.

Чтобы сберечь силы своей армии, король Ректилании хочет установить блокаду столичной провинции, захватив как можно меньше провинций. Помогите ему выяснить, сколько провинций требуется захватить. Захватывать столичную провинцию нельзя, поскольку для этого сил армии Ректилании пока недостаточно.

Входные данные
В первой строке вводятся числа M и N (3 <= M, N <= 200). Следующие M строк содержат N символов каждая и задают карту Флатландии. Символ, находящийся в i + 1-й строке входных данных на j-м месте, представляет собой символ провинции, которой принадлежит квадратик (i, j). Все символы имеют ASCII-код больше 32 (пробела).

Выходные данные
Выведите единственное число - количество провинций, которые требуется захватить. Если установить блокаду невозможно, выведите "-1".

В точке (0, 0) координатной плоскости расположена лампочка, которая представляет собой точечный источник света. Неподалеку от лампочки находится дом Пети, который представляет собой выпуклый многоугольник с N вершинами. Сам Петя находится в точке с координатами (x, y).

Петя хочет увидеть свет. Для этого ему необходимо оказаться в такое точке, что отрезок, соединяющей ее с началом координат, не пересекается с домом Пети (но может его касаться, в частности, проходить вдоль стороны многоугольника дома).

Петя может перемещаться по плоскости со скоростью v. Разумеется, Петя не может проходить сквозь дом (хотя он может двигаться по его границе).

Выясните, какое минимальное время требуется Пете, чтобы оказаться в освещенной точке.


Входные данные
В первой строке вводятся координаты Пети – два неотрицательных вещественных числа, не превышающих 1000, и его скорость v – вещественное число, 10^-2≤ v≤ 10⁴.

Вторая строка содержит N – число вершин в многоугольнике, задающем Петин дом ( 3≤N≤100). Далее в N строках вводится по два вещественных числа – координаты вершин многоугольника в порядке их обхода против часовой стрелки. Все координаты неотрицательны и не превышают 1000.

Гарантируется, что входные данные корректны, в частности, многоугольник выпуклый, и никакие три его последовательные вершины не лежат на одной прямой. Также гарантируется, что и Петя, и лампочка находятся снаружи от многоугольника, в частности, не находятся на его границе. Расстояние от точки, где находится Петя, до многоугольника и от начала координат до многоугольника не меньше 10^-2, расстояние от Пети до начала координат не меньше 10^-2.

Выходные данные
Выведите минимальное время, за которое Петя сможет попасть в освещенную точку. Ваш ответ должен отличаться от правильного не более чем на 10^-4.

В столице одной Очень Демократической Страны все жители в 8 часов утра одновременно выходят со станций метро, ближайших к месту своей работы, и дальше добираются до работы на автобусах. Мэр города хочет построить еще одну станцию метро так, чтобы после этого время, к которому все люди доберутся до места своей работы (то есть время, когда последний работник окажется на работе), было наименьшим возможным.

Автобусное сообщение в столице устроено следующим образом. Есть N автобусных остановок, в частности, возле каждой станции метро расположено по остановке. Между N – 1 парой остановок постоянно курсируют автобусы, время движения от одной остановки до другой – 1 минута. Временем ожидания и пересадки можно пренебречь. Автобусное сообщение в столице организовано так, что от любой автобусной остановки до любой другой можно добраться на автобусах (возможно, с пересадками).

Входные данные
В первой строке входных данных содержатся два числа N и M – количество автобусных остановок и станций метро соответственно (2 ≤ N ≤ 50 000, 1 ≤ M ≤ 1 000, M < N).

Во второй строке задаются через пробел M чисел – номера автобусных остановок, рядом с которыми есть станции метро (каждая – не более одного раза).

В следующих N – 1 строках записано по два числа – номера автобусных остановок, между которыми курсирует автобус. (Автобус ходит в обоих направлениях. Каждый маршрут указан один раз.)

Выходные данные
Выведите два числа – сначала наибольшее время за которое кто-то будет и после строительства добираться на работу, а затем номер автобусной остановки, рядом с которой следует построить новую станцию метро. (Строить можно возле тех автобусных остановок, возле которых еще нет станций метро). Если решений несколько, выведите одно из них.
 

В ежегодном чемпионате Флатландии (которая, естественно, является плоским миром) по космическим гонкам "Формула-3" участвуют N космических скутеров, имеющие форму треугольников. До начала гонок скутеры занимают положение в стартовой зоне согласно результатам жеребьевки.


Скутеры стартуют строго по порядку. Каждый скутер,получив команду «старт», уезжает в положительном направлении оси Ox. Следующий скутер стартует лишь тогда, когда предыдущий покинет стартовую зону. Скутеры уезжают строго параллельно оси Ox, скутеры в стартовой зоне не поворачивают и не разворачиваются.

Естественно, что если в момент старта на пути скутера окажется другой скутер, то произойдет авария (даже если скутер заденет лишь угол другого скутера своим углом).

Для уменьшения опасности столкновения скутеров на старте строго соблюдается следующее правило: прямые, параллельные оси Ox и пересекающие какой-то скутер, должны в совокупности пересекать не более 100 других скутеров (прямая, проходящая через одну точку скутера также считается прямой, пересекающей скутер). Например, на приведенном рисунке прямые, параллельные Ox и пересекающие скутер 2, проходят через 2 других скутера (1 и 3), а прямые, проходящие через скутер 1, проходят только через один другой скутер (номер 2).

Главный Судья гонок хочет определить порядок, в котором должны стартовать скутеры, чтобы аварии не произошло. Например, в ситуации, приведенной на рисунке, сначала должен стартовать скутер номер 2 (если попытается стартовать скутер номер 1 или 3, то он столкнется со скутером номер 2). После этого скутеры 1 и 3 могут стартовать в любом порядке (они друг другу не мешают).

Помогите Главному Судье — напишите программу, которая определит какой-нибудь порядок старта скутеров, чтобы аварии не произошло.

Входные данные
В первой строке вводится натуральное число N( 1 ≤ N ≤ 30 000).

В каждой из следующих N строк содержится по 6 чисел: x₁, y₁, x₂, y₂, x₃, y₃ – координаты трех вершин скутера на старте, целые числа, не превосходящие по модулю 10⁶. В начальный момент скутеры не задевают друг друга.

Выходные данные
Выведите через пробел N чисел – номера скутеров в том порядке, в котором они могут стартовать. Если решений несколько, выведите одно любое из них. Если решений нет, выведите одно число -1.

Примечание
Первый тест соответствует приведенному рисунку. Ответ 2 3 1 в этом тесте также является правильным