Diplomacy

You are a senator in an ancient empire ruled by a dictator. You have joined a secret committee of senators from both parties that is plotting to overthrow him. The plot succeeds only if every state in the empire backs it, and that requires every state governor to belong to the same party.

Right now each governor belongs to either the Orange Party or the Purple Party. You are confident that you can get either party behind the plot, so it does not matter which party wins out in the end.

The committee has studied the political situation. Two governors influence each other when they are friends and belong to the same party. Each month one lobbyist does whatever it takes to make a single governor switch parties. When that happens, every friend of that governor who belonged to the same party switches as well, and so do the friends of those friends who belonged to that party, and the change keeps spreading. To avoid suspicion the committee alternates Orange and Purple lobbyists from month to month. In the first month it may start with either party.

The committee also knows which governors are friends. The friendship graph is connected, so there is no isolated group whose members are friends only with each other.

Find the minimum number of months needed for every governor to belong to the same party.

The input contains several test cases. The first line of each test case has two integers $n$ and $m$ ($1 \le n \le 100$, $n - 1 \le m \le n(n-1)/2$), where $n$ is the number of governors and $m$ is the number of known friendships. The second line has $n$ integers, each 0 or 1, giving the current party of governors 1 through $n$ in order. 0 is Orange and 1 is Purple. Each of the next $m$ lines has two integers $a$ and $b$ ($1 \le a < b \le n$), meaning that governor $a$ and governor $b$ are friends. Friendship goes both ways: if $a$ is a friend of $b$, then $b$ is a friend of $a$. All $m$ pairs $(a, b)$ are distinct. In every test case the friendship graph is connected. The input ends with a line holding two zeros, and that line is not a test case.

For each test case, print one integer, the minimum number of months needed for every governor to belong to the same party. Print one integer per line, and do not print blank lines between them.