적대 국가

시간 제한1초메모리 제한128 MB

요약

미정인 도시를 두 국가 중 하나에 배정해 양쪽을 잇는 도로 수를 최소화합니다.

난이도: 보통10점 중 7점
유형: 그래프
정답자: 아직 제출이 없습니다

문제

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입니다.

예제5

예제 1
입력
```
4 4
1 1 3 2
1 2
1 3
2 3
3 4
```
예상 출력
```
1
```
예제 2
입력
```
3 2
1 3 2
1 2
2 3
```
예상 출력
```
1
```
예제 3
입력
```
2 1
1 2
1 2
```
예상 출력
```
1
```
예제 4
입력
```
4 2
1 1 2 2
1 3
2 4
```
예상 출력
```
2
```
예제 5
입력
```
4 4
1 3 3 2
1 2
1 3
2 4
3 4
```
예상 출력
```
2
```