- محدودیت زمان: ۱ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
- آزمون عملی اول فاینال سی و دومین دوره المپیاد کامپیوتر ایران
بعد از دیدن فیلم ماداگاسکار، علیجان عاشق شخصیت گورخر شد و تحقیقات خودش را روی این گونه از جانوران آغاز کرد. او جدیدا متوجه شده در یکی از پارکهای ملی، گورخری وجود دارد که رنگ بدن او بسیار جالب است.
علیجان بدن گورخر را به یک گراف بدونجهت و همبند شبیهسازی کرد که هر راس آن سیاه یا سفید است. گورخر این قابلیت را دارد که یکی از رئوسش مانند \(v\) را انتخاب کنیم و رنگ تمام رئوس مولفه همبندی همرنگ با \(v\) عوض شود. به بیانی دیگر، رنگ راس \(u\) عوض میشود اگر مسیری از \(v\) به \(u\) وجود داشته باشد که تمام رئوس آن همرنگ هستند.
علیجان عاشق گورخرها است و دوست ندارد که تمام رئوس مربوط به بدن گورخر همرنگ شود. برای اینکه بتواند از گورخر محافظت کند، نیاز دارد تا کمترین عملیات ممکن برای همرنگ شدن تمامی رئوس را پیدا کند. به او در پیدا کردن این مقدار کمک کنید.
برای درک بهتر سوال، به توضیحات نمونههای ورودی توجه کنید.
ورودی
در خط اول ورودی دو عدد طبیعی \(n\) تعداد رئوس و \(m\) عداد یالها بهترتیب میآیند.
\[1 \leq n \leq 2000\] \[1 \leq m \leq 5000\]
در خط دوم ورودی \(c_1, c_2, \cdots c_n\) بهترتیب میآیند. \(c_i\) مربوط به رنگ راس \(i\) ام میباشد. مقدار \(0\) بیانگر رنگ سفید و مقدار \(1\) بیانگر راس سیاه است. \[0 \leq c_i \leq 1\] در هر یک از \(m\) خط بعدی، دو سر هر یال \(v_i\) و \(u_i\) میآید. \[1 \leq v_i, u_i \leq n\]
خروجی
در تنها خط خروجی، کمترین عملیات ممکن برای اینکه گورخر تکرنگ شود را چاپ کنید.
زیرمسئلهها
| زیرمسئله | نمره | محدودیت |
|---|---|---|
| ۱ | ۱۰ | \(n \le 20\) |
| ۲ | ۱۰ | \(m = n-1\) و به ازای هر \(1 \leq i \leq n - 1\) یک یال بین رئوس \(i\) و \(i+1\) وجود دارد. |
| ۳ | ۴۰ | \(m = n-1\) |
| ۴ | ۴۰ | بدون محدودیت اضافی |
مثال
ورودی نمونه ۱
7 8
1 0 0 1 1 0 1
1 2
1 3
2 4
3 4
4 5
4 6
5 7
6 7
خروجی نمونه ۱
2
علیجان میتواند در دو مرحله با انتخاب رئوس ۴ و ۱ همه رئوس گراف را سفید کند.
ورودی نمونه ۲
9 8
1 0 1 0 1 0 1 0 1
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
خروجی نمونه ۲
4