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

به شما یک گراف بدون جهت داده‌اند. شما باید یال‌های این گراف را با رنگ‌های $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