- محدودیت زمان: ۱ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
به شما یک گراف بدون جهت دادهاند. شما باید یالهای این گراف را با رنگهای $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
ارسال پاسخ برای این سؤال