Мэр города решил, что по городу стало ездить чересчур много маршруток, и из-за этого жители перестали пользоваться трамваями. Следовало провести реорганизацию фирмы, управляющей всеми маршрутными такси в городе. А в том городе, если вы не знали, было N остановок машруток, некоторые из которых были соединены дорогой. Если две остановки соединены дорогой, то маршрутка может без дополнительных остановок доехать как от первой остановки до второй, так и от второй до первой. Также известно, что никакая пара остановок не соединена двумя и более дорогами и никакая дорога не соединяет остановку с самой собой. Маршрутка останавливается на всех остановках на пути следования. После поступления приказа уменьшить количество маршрутов фирма решила оставить только кольцевые маршруты, содержащие не менее трёх различных остановок, при следовании по которым маршрутка не проезжает через одну остановку 2 раза. Кроме того, любая пара маршрутов отныне должна отличаться хотя бы по одной дороге. Фирма не хотела сдавать позиции в выгодном бизнесе, поэтому решила создать наибольшее количество маршрутов, удовлетворяющее данным двум требованиям. Маршруты были пронумерованы числами от 1 до K (K — количество маршрутов). По каждому маршруту ездил ровно один микроавтобус.

Вторая задача, вставшая перед фирмой — составить расписание работы контролёров. Расписание представляет собой таблицу, столбцами которой являются маршруты, а строками — моменты времени, в которые производится контроль. Если в клетке [T, I] стоит число X, это означает, что микроавтобус, следующий по маршруту номер I, останавливается для контроля на остановке номер X в момент времени T. Клетка может быть и пуста. Известно, что в течение дня каждая маршрутка должна останавливаться на каждой остановке для контроля ровно один раз, то есть в каждом столбце столько непустых клеток, сколько остановок в маршруте. Кроме того, в один и тот же момент времени на одной остановке не должны проверять 2 маршрутки, и, конечно, одна маршрутка не может в один момент времени находиться на двух разных остановках. Требуется найти минимально возможное число строк в такой таблице.

В первой строчке входа находится целые числа N и M — количество остановок и дорог в городе соответственно. 3 ≤ N ≤ 14. В следующих M строках перечислены пары остановок, соединяемых очередной дорогой — числа от 1 до N.

Выведите целое число — минимальное количество строк в расписании.