你是一个古老帝国的参议院议员，该帝国由一位强权独裁者统治。你加入了一个由参议院两党组成的秘密委员会，正密谋推翻这位独裁者。

为了使阴谋成功，帝国中所有的州最终都必须支持该计划——而要实现这一点，所有州的州长都需要属于同一个党派。

目前，每位州长要么是橙党（Orange Party）成员，要么是紫党（Purple Party）成员。由于你确信自己可以让任何一个党派支持该计划，因此最终哪个党派获胜并不重要。

秘密委员会研究了政治局势，确定如果两位州长互为朋友且属于同一党派，他们就会相互影响。为了争取所有州长加入，每个月都会有一名说客不惜一切代价让一名州长转换党派。当这种情况发生时，该州长所有属于同一党派的朋友也会转换党派，这些朋友的朋友（如果也在该党派内）也会转换，以此类推。为了避免怀疑，秘密委员会每个月会轮流派遣橙党/紫党说客。他们可以在第一个月选择从任何一个党派开始。

秘密委员会还知道哪些州长互为朋友，每位州长至少与另一位州长是朋友，并且不存在仅与彼此为友的孤立群体。

你的任务是确定所有州长属于同一党派所需的最少月数。一旦实现这一点，阴谋的下一步就可以实施了。

输入格式

输入包含多个测试用例。每个测试用例的第一行包含两个整数 $n$ ($1 \le n \le 100$) 和 $m$ ($n-1 \le m \le n(n-1)/2$)，其中 $n$ 是州长的数量，$m$ 是已知的友谊关系数量。下一行包含 $n$ 个整数，均为 0 或 1，按顺序表示州长当前的党派归属（0=橙党，1=紫党）。接下来的 $m$ 行，每行包含两个整数 $a$ 和 $b$ ($1 \le a < b \le n$)，表示州长 $a$ 和州长 $b$ 是朋友。正如现实生活中一样，友谊是双向的：如果 $a$ 是 $b$ 的朋友，那么 $b$ 也是 $a$ 的朋友。所有 $m$ 对 $(a, b)$ 都是唯一的。输入以一行两个 0 结束。

输出格式

对于每个测试用例，输出一个整数，表示所有州长属于同一党派所需的最少月数。每个整数占一行，不要包含空格。输出之间不要打印空行。

样例

输入 1

4 3
0 1 0 0
1 2
2 3
2 4
5 4
0 1 1 0 1
1 2
2 3
3 4
4 5
0 0

输出 1

1
2