Description

In a kindergarten, there are $n$ children who plan to decide whether to take a nap by voting.

This issue is not very important to them, so they decide to be considerate.

Although everyone has their own preference, they may cast a vote opposite to their original intention to accommodate their friends.

We define the conflict count of a voting result as the sum of the following two quantities:

• The number of friend pairs whose actual votes differ.
• The number of children whose actual vote differs from their original preference.

Our problem is: how should each child vote to minimize the conflict count?

Input Format

The first line contains two integers $n, m$, where $n$ is the total number of children and $m$ is the number of friend pairs.

The second line contains $n$ integers. The $i$-th integer is the $i$-th child’s preference: $1$ means agreeing to take a nap, and $0$ means opposing it.

The next $m$ lines each contain two integers $i, j$, indicating that $i$ and $j$ are a pair of friends. We guarantee that any pair $i, j$ does not repeat.

Output Format

Output a single integer on one line: the minimum possible conflict count.

3 3
1 0 0
1 2
1 3
3 2

1

Hint

For $100\%$ of the testdata, $2 \le n \le 300$, $1 \le m \le \frac{n(n-1)}{2}$.

Translated by ChatGPT 5