بعد از دیدن فیلم ماداگاسکار، علی‌جان عاشق شخصیت گورخر شد و تحقیقات خودش را روی این گونه از جانوران آغاز کرد. او جدیدا متوجه شده در یکی از پارک‌های ملی، گورخری وجود دارد که رنگ بدن او بسیار جالب است.

علی‌جان بدن گورخر را به یک گراف بدون‌جهت و همبند شبیه‌سازی کرد که هر راس آن سیاه یا سفید است. گورخر این قابلیت را دارد که یکی از رئوسش مانند $v$ را انتخاب کنیم و رنگ تمام رئوس مولفه همبندی همرنگ با $v$ عوض شود. به بیانی دیگر، رنگ راس $u$ عوض می‌شود اگر مسیری از $v$ به $u$ وجود داشته باشد که تمام رئوس آن همرنگ هستند.

علی‌جان عاشق گورخرها است و دوست ندارد که تمام رئوس مربوط به بدن گورخر همرنگ شود. برای اینکه بتواند از گورخر محافظت کند، نیاز دارد تا کمترین عملیات ممکن برای همرنگ شدن تمامی رئوس را پیدا کند. به او در پیدا کردن این مقدار کمک کنید.

برای درک بهتر سوال، به توضیحات نمونه‌های ورودی توجه کنید.

در خط اول ورودی دو عدد طبیعی $n$ تعداد رئوس و $m$ تعداد یال‌ها به‌ترتیب می‌آیند.

در خط دوم ورودی $c_1, c_2, \cdots c_n$ به‌ترتیب می‌آیند. $c_i$ مربوط به رنگ راس $i$ ام می‌باشد. مقدار $0$ بیانگر رنگ سفید و مقدار $1$ بیانگر راس سیاه است.

در هر یک از $m$ خط بعدی، دو سر هر یال $v_i$ و $u_i$ می‌آید.

در تنها خط خروجی، کمترین عملیات ممکن برای اینکه گورخر تک‌رنگ شود را چاپ کنید.

• زیرمسئله اول (۱۰ نمره): $n \leq 20$
• زیرمسئله دوم (۱۰ نمره): $m = n-1$ و به ازای هر $1 \leq i \leq n - 1$ یک یال بین رئوس $i$ و $i + 1$ وجود دارد.
• زیرمسئله سوم (۴۰ نمره): $m = n - 1$
• زیرمسئله چهارم (۴۰ نمره): بدون محدودیت اضافی

• محدودیت زمان: ۱ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت
• $1 \leq n \leq 2000$
• $1 \leq m \leq 5000$
• $0 \leq c_i \leq 1$
• $1 \leq v_i, u_i \leq n$

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 

• سوال بعد