eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Спички

Спички

\textit{Спички детям не игрушка!} \textit{Инструктаж по пожарной безопасности} На игре "Форт Бойярд" команде лкшат вполне могут предложить следующую задачу: на столе лежат \textbf{n} спичек; требуется удалить ровно \textbf{k} из них так, чтобы в полученной конфигурации присутствовало ровно \textbf{m} квадратов. \InputFile В первой строке входного файла содержатся целые числа \textbf{n}, \textbf{k} и \textbf{m} (\textbf{0} < \textbf{k} < \textbf{n} < \textbf{25}, \textbf{0} ≤ \textbf{m} ≤ \textbf{50}). В каждой из следующих \textbf{n} строк содержится описание очередной спички - четыре целых числа \textbf{x_\{i,1\}}, \textbf{y_\{i,1\}}, \textbf{x_\{i,2\}}, \textbf{y_\{i,2\}}, задающие координаты концов спички. Длина каждой спички равна \textbf{1}. Никакие две спички не совпадают. Координаты не превышают \textbf{100} по абсолютной величине. \OutputFile Если получить ровно \textbf{m} квадратов нельзя, выведите в выходной файл единственное число \textbf{-1}. В противном случае выведите \textbf{k} чисел - номера спичек, которые следует удалить. Спички нумеруются с единицы. Если решений несколько, выведите любое из них.
Лимит времени 2 секунды
Лимит использования памяти 64 MiB
Входные данные #1
7 1 0
1 1 1 2
2 1 2 2
3 1 3 2
1 1 2 1
2 1 3 1
1 2 2 2
2 2 3 2
Выходные данные #1
2
Автор Ю.Петров, М.Дворкин