یک تقاطع با n خیابان منتهی به آن داریم. می خواهیم به وسیله یک چراغ راهنمای چندزمانه، بارترافیکی این تقاطع را کنترل کنیم.
برای هردو خیابان x و y منتهی به این تقاطع، لازم است در دست کم یکی از زمان‌های این چراغ راهنما، امکان عبور امن بین x و y وجود داشته باشد. عبور امن عبوری است که در آن اجازه عبور از خیابانی مثل z به خیابانی مثل t که عبور همزمان خودرو از آن منجر به تصادف با خودروی عبوری از x و y می‌شود، داده نشده باشد. دقت کنید که خیابان‌های منتهی به چهارراه دوطرفه هستند، بنابراین عبور از x به y معادل عبور از y به x نیست.
برنامه‌ای بنویسید که حداقل تعداد زمان‌های این چراغ راهنما را محاسبه کند.
ورودی:
خط اول ورودی شامل n، تعداد خیابان‌ها و m تعداد عبورهای حادثه‌ساز است. ورودی با m خط دنبال می‌شود که در هر خط ۴ عدد x y z t داده خواهد شد، به این معنی که اگر همزمان بین دو خیابان x و y و دو خیابان z و t عبور انجام گیرد، حادثه‌ساز خواهد بود.
خروجی:
در تنها سطر خروجی، حداقل تعداد زمان‌های این چراغ را چاپ کنید.
محدودیت‌ها:
$$ n \leq 12 $$
$$ m \leq 1000 $$
مثال:
input:
1 4
1 2 3 4
output:
2