You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

幼儿园里有 $n$ 个小朋友打算通过投票来决定睡不睡午觉。

对他们来说，这个问题并不是很重要，于是他们决定发扬谦让精神。

虽然每个人都有自己的主见，但是为了照顾一下自己朋友的想法，他们也可以投和自己本来意愿相反的票。

我们定义一次投票的冲突数为下面两者相加：

• 实际投票不同的好朋友对数。

• 自己实际投票和自己本来意愿不同的人数。

我们的问题就是，每位小朋友应该怎样投票，才能使冲突数最小？

输入格式

第一行两个整数 $n,m$。其中 $n$ 代表总人数，$m$ 代表好朋友的对数。

第二行 $n$ 个整数，第 $i$ 个整数代表第 $i$ 个小朋友的意愿：当它为 $1$ 时表示同意睡觉，当它为 $0$ 时表示反对睡觉。

接下来 $m$ 行，每行有两个整数 $i,j$，表示 $i,j$ 是一对好朋友，我们保证任何两对 $i,j$ 不会重复。

输出格式

一行一个整数，即可能的最小冲突数。

3 3
1 0 0
1 2
1 3
3 2

1

提示

对于 $100\%$ 的数据，$2\le n\le300$，$1\le m \le \frac{n(n-1)}2$。