Контроль за розкладом

Мер міста помітив, що через велику кількість маршруток жителі перестали користуватись трамваями. Тому компанія, що керує всіма маршрутками, вирішила провести реорганізацію. В місті є $N$ зупинок маршруток, деякі з яких з'єднані дорогами. Якщо дві зупинки з'єднані дорогою, маршрутка може їхати між ними в обох напрямках без додаткових зупинок. Жодна пара зупинок не з'єднана більше ніж однією дорогою, і жодна дорога не з'єднує зупинку саму з собою. Маршрутка зупиняється на кожній зупинці свого маршруту. Після наказу скоротити кількість маршрутів залишили лише кільцеві маршрути, які містять не менше трьох різних зупинок та не проходять через одну і ту ж зупинку більше одного разу. Крім того, будь-які два маршрути мають відрізнятись хоча б однією дорогою. Компанія вирішила створити найбільшу можливу кількість таких маршрутів, пронумерувавши їх від $1$ до $K$ ($K$ — кількість маршрутів). По кожному маршруту їздить лише одна маршрутка.

Друга задача — скласти розклад для контролерів. Розклад — це таблиця, де стовпці — маршрути, а рядки — моменти часу, коли відбувається контроль. Якщо в клітинці [T, I] стоїть число $X$, це означає, що в момент часу $T$ маршрутка на маршруті $I$ проходить контроль на зупинці $X$. Клітинка може бути порожньою. Відомо, що за день кожна маршрутка має пройти контроль на кожній своїй зупинці рівно один раз, тобто в кожному стовпці таблиці стільки непорожніх клітинок, скільки зупинок у маршруті. В той самий момент часу на одній і тій же зупинці не можуть одночасно проходити контроль дві маршрутки, а маршрутка не може бути на двох зупинках одночасно. Знайдіть мінімально можливу кількість рядків у таблиці.