P16176 [ICPC 2014 NAIPC] Diplomacy

你是一个由强大独裁者统治的古代帝国的参议员。你加入了一个由参议院两党成员组成的秘密委员会，该委员会正在密谋推翻独裁者。 为了使密谋成功，至关重要的是帝国中的所有州最终都要支持该计划——为了实现这一点，所有州的州长都需要成为同一党派的成员。 目前，每位州长要么是橙党（Orange Party）成员，要么是紫党（Purple Party）成员。由于你有信心让任何一方支持密谋，因此最终哪一方获胜并不重要。 秘密委员会研究了政治局势，并确定：如果两位州长是朋友关系且属于同一党派，他们就会相互影响。为了让所有州长都加入计划，每月会有一次游说活动，游说者会尽一切努力让一位州长转换党派。当这种情况发生时，该州长的所有属于同一党派的朋友也会随之转换党派，这些朋友的朋友也会在党内转换，依此类推。为了不被察觉，秘密委员会将每月交替派遣橙党/紫党的游说者。他们可以在第一个月从任意一个党派开始。 秘密委员会还知道哪些州长是朋友关系，每位州长至少有一位朋友，并且不存在只与彼此为朋友的孤立群体。 你的任务是确定所有州长成为同一党派成员所需的最少月数。一旦达到这一状态，密谋的后续步骤就可以进行。

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

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

翻译由 DeepSeek V3.2 完成