외교

고대 제국의 원로원 의원인 당신은 독재자를 몰아내려는 초당파 비밀 위원회에 들어갔다. 계획이 성공하려면 제국의 모든 주가 계획을 지지해야 하고, 그러려면 모든 주지사가 같은 정당에 속해야 한다.

지금 각 주지사는 주황당이나 보라당 중 한 곳에 속한다. 두 정당 중 어느 쪽이든 계획을 지지하게 만들 수 있으니, 마지막에 어느 정당으로 통일되는지는 상관없다.

비밀 위원회가 조사한 정치 상황은 이렇다. 두 주지사는 서로 친구이면서 같은 정당에 속할 때 서로에게 영향을 준다. 매달 로비스트 한 명이 수단을 가리지 않고 주지사 한 명의 소속 정당을 바꾼다. 그러면 그 주지사와 같은 정당이던 친구도 함께 정당을 옮기고, 그 친구의 친구 중 같은 정당이던 사람도 따라 옮기며, 변화는 이렇게 계속 번져 나간다. 의심을 사지 않으려고 위원회는 주황당 로비스트와 보라당 로비스트를 매달 번갈아 보낸다. 첫 달에는 두 정당 중 어느 쪽으로 시작해도 된다.

위원회는 어떤 주지사끼리 친구인지도 알고 있다. 친구 관계 그래프는 연결되어 있어서, 자기들끼리만 친구인 고립된 무리는 없다.

모든 주지사가 같은 정당에 속하는 데 필요한 최소 개월 수를 구하라.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스의 첫 줄에는 정수 $n$과 $m$이 주어진다 ($1 \le n \le 100$, $n - 1 \le m \le n(n-1)/2$). $n$은 주지사의 수이고, $m$은 알려진 친구 관계의 수다. 둘째 줄에는 1번부터 $n$번까지 주지사의 현재 소속 정당을 나타내는 0 또는 1이 순서대로 $n$개 주어진다. 0은 주황당, 1은 보라당이다. 이어지는 $m$개의 줄에는 각각 두 정수 $a$와 $b$가 주어지며 ($1 \le a < b \le n$), 주지사 $a$와 주지사 $b$가 친구라는 뜻이다. 친구 관계는 양방향이라서 $a$가 $b$의 친구이면 $b$도 $a$의 친구다. $m$개의 쌍 $(a, b)$는 모두 서로 다르다. 각 테스트 케이스에서 친구 관계 그래프는 연결되어 있다. 입력의 마지막 줄에는 0이 두 개 주어지며, 이 줄은 테스트 케이스가 아니다.

각 테스트 케이스마다 모든 주지사가 같은 정당에 속하는 데 필요한 최소 개월 수를 정수 하나로 출력한다. 정수는 한 줄에 하나씩 출력하고, 출력 사이에 빈 줄을 넣지 않는다.