• محدودیت زمان: ۱ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

---

به شما یک گراف بدون جهت داده‌اند. شما باید یال‌های این گراف را با رنگ‌های \(0, 1, 2\) طوری رنگ‌آمیزی کنید که:

• جمع رنگ تمامی یال‌ها کمینه شود.
• برای هر یالی که با رنگ \(0\) رنگ‌آمیزی می‌کنید، بایستی همسایه‌ای وجود داشته باشد که رنگ آن \(2\) باشد. دو یال همسایه‌اند اگر راسی مشترک داشته باشند.

اطلاعیه: محدودیت تعداد یال‌ها را به جای ۳۰ مقدار ۴۰ درنظر بگیرید.

ورودی

در خط اول ورودی به ترتیب \(n\) و \(m\) آمده است که نشان‌دهنده‌ی تعداد رئوس گراف و تعداد یال‌های آن می‌باشد.

در \(m\) خط بعدی، در هر خط شماره رئوس دو سر یکی از یال‌ها آمده است.

\[1 \leq n \leq 20\] \[1 \leq m \leq 40\]

خروجی

در خروجی مجموع رنگ تمامی یال‌ها در رنگ‌آمیزی کمینه را چاپ کنید.

مثال

ورودی نمونه ۱

3 3
1 2
2 3
1 3

خروجی نمونه ۱

2

ورودی نمونه ۲

18 27
1 2
1 4
1 6
3 2
3 4
3 6
2 5
4 5
7 8
7 10
7 12
9 8
9 10
9 12
8 11
10 11
13 14
13 16
13 18
15 14
15 16
15 18
14 17
16 17
5 11
12 17
18 6

خروجی نمونه ۲

14