#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
#include <climits>

using namespace std;

struct puperfunctionmycreateion {
	int data, prev, st, ans;
};
int find228(queue <puperfunctionmycreateion>, int);
int find1337(queue <puperfunctionmycreateion>, int);

int main()
{
	puperfunctionmycreateion temp, temp1;
	int n, m, free = 0, v, u, h;
	vector <int> a, head, ans, next, dest, mark, ans1;
	queue <puperfunctionmycreateion> q;
	cin >> n >> m;
	mark.reserve(100000);
	head.reserve(100000);
	a.reserve(100000);
	ans.reserve(100000);
	dest.reserve(100000);
	next.reserve(100000);
	head.resize(n);
	ans.resize(n);
	a.resize(n);
	mark.resize(n);
	next.resize(n);
	for (int i = 1; i <= n; i++) {
		next[i] = 0;
		mark[i] = 0;
		ans[i] = INT_MAX - 20;
		mark[i] = 0;
		cin >> a[i];
		if (a[i] != 0) {
			temp.data = i;
			temp.st = i;
			temp.ans = 0;
			temp.prev = 0;
			q.push(temp);
			mark[i] = 1;
		}
	}
	for (int i = 1; i <= m; i++) {
		cin >> v >> u;
		free++;
		dest.resize(free + 3);
		next.resize(free + 3);
		dest[free] = u;
		next[free] = head[v];
		head[v] = free;
		free++;
		dest[free] = v;
		next[free] = head[u];
		head[u] = free;
	}
	while (!q.empty()) {
		temp = q.front();
		q.pop();
		h = head[temp.data];
		while (h) {
			if (dest[h] != temp.prev)
				if (!mark[dest[h]]) {
					temp1.data = dest[h];
					temp1.st = temp.st;
					temp1.ans = temp.ans + 1;
					temp1.prev = temp.data;
					q.push(temp1);
					mark[dest[h]] = 1;
				}
				else
                    if (a[temp.st] != a[find1337(q, dest[h])])
					if (a[dest[h]] == 0)
						ans[temp.st] = temp.st + find228(q, dest[h]);
					else
						ans[dest[h]] = temp.ans + 1;
			h = next[h];
		}
	}
	int min2;
	min2 = ans[1];
	for (int i = 1; i <= n; i++)
		//min2 = min(min2, ans[i]);
		cout << ans[i] << endl;
	cout << min2 << "\n";
	return 0;
}

int find228(queue <puperfunctionmycreateion> f, int data1) {
	int ans1;
	while (!f.empty()) {
		if (f.front().data == data1)
			ans1 = f.front().ans;
		f.pop();
	}
	return ans1;
}

int find1337(queue <puperfunctionmycreateion> f, int data1) {
	int ans1;
	while (!f.empty()) {
		if (f.front().data == data1)
			ans1 = f.front().st;
		f.pop();
	}
	return ans1;
}