Hostile States

Time limit1sMemory limit128 MB

Summary

Assign each undecided city to one of two states to minimize the number of roads crossing between states.

Level: Medium7 of 10
Topics: Graph
Solved: No attempts yet

Problem

Bitocja and Bajtocja are about to sign a truce after a long war. The two states must decide which state each city belongs to. Their rulers agreed to split the cities so as to minimize the number of roads that directly connect a pair of cities belonging to different states.

After the truce is signed, report how many such roads connect the two states.

Input

The first line contains the number of cities $n$ and the number of roads $m$ ( $1 \le n \le 500$ , $0 \le m \le n(n-1)/2$ ).

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ( $1 \le a_i \le 3$ ). If $a_i = 1$ , city $i$ belongs to Bitocja; if $a_i = 2$ , city $i$ belongs to Bajtocja; if $a_i = 3$ , city $i$ must be assigned to either Bitocja or Bajtocja.

Each of the next $m$ lines contains two integers $a$ , $b$ ( $1 \le a < b \le n$ ), meaning that cities $a$ and $b$ are joined by a direct road. No pair $(a, b)$ appears more than once.

Output

Print a single integer: the minimum possible number of roads connecting a city of Bitocja with a city of Bajtocja after the truce is signed.

Hint

In the first example, city 3 is the only unassigned city. Assigning it to Bitocja leaves just one road between the two states, the road between cities 3 and 4, whereas assigning it to Bajtocja would leave two such roads. Hence the minimum is 1.

Examples5

Example 1
Input
```
4 4
1 1 3 2
1 2
1 3
2 3
3 4
```
Expected output
```
1
```
Example 2
Input
```
3 2
1 3 2
1 2
2 3
```
Expected output
```
1
```
Example 3
Input
```
2 1
1 2
1 2
```
Expected output
```
1
```
Example 4
Input
```
4 2
1 1 2 2
1 3
2 4
```
Expected output
```
2
```
Example 5
Input
```
4 4
1 3 3 2
1 2
1 3
2 4
3 4
```
Expected output
```
2
```