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