적대 국가

Bitocja와 Bajtocja는 오랜 전쟁 끝에 휴전 협정을 맺으려 합니다. 두 나라는 각 도시를 어느 나라에 귀속시킬지 결정해야 합니다. 두 나라의 통치자들은 서로 다른 나라에 속한 도시 쌍을 직접 잇는 도로의 수가 최소가 되도록 도시를 나누기로 했습니다.

휴전 협정을 맺은 뒤 서로 다른 나라를 잇는 이러한 도로가 몇 개가 되는지 구하세요.

첫째 줄에 도시의 수 $n$과 도로의 수 $m$이 주어집니다 ($1 \le n \le 500$, $0 \le m \le n(n-1)/2$).

둘째 줄에 $n$개의 정수 $a_1, a_2, \ldots, a_n$이 주어집니다 ($1 \le a_i \le 3$). $a_i = 1$이면 도시 $i$는 Bitocja에 속하고, $a_i = 2$이면 도시 $i$는 Bajtocja에 속하며, $a_i = 3$이면 도시 $i$는 Bitocja와 Bajtocja 중 한쪽에 배정해야 합니다.

이어지는 $m$개의 줄에는 각각 두 정수 $a$, $b$가 주어지며 ($1 \le a < b \le n$), 도시 $a$와 도시 $b$가 도로로 직접 연결되어 있음을 뜻합니다. 같은 쌍 $(a, b)$는 두 번 주어지지 않습니다.

휴전 협정을 맺은 뒤 Bitocja의 도시와 Bajtocja의 도시를 잇는 도로의 최소 개수를 정수 하나로 출력하세요.

첫 번째 예제에서는 도시 3만 배정되지 않은 상태입니다. 도시 3을 Bitocja에 배정하면 서로 다른 나라를 잇는 도로는 도시 3과 도시 4 사이의 도로 하나뿐입니다. 반대로 Bajtocja에 배정하면 그러한 도로가 두 개가 됩니다. 따라서 최솟값은 1입니다.