یک تقاطع با $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
```