题目描述

幼儿园里有 $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

数据规模与约定

$2 \le n \le 300,1 \le m \le \dfrac{n(n-1)}{2}$。

提示

在第一个例子中，所有小朋友都投赞成票就能得到最优解。

题目来源

Day2