时间限制：1500ms　内存限制：512MB

题目描述

程老师学校的配电房最近装了一套新系统：$n$ 盏灯排成一列，每盏灯有三个档位——$0$ 表示关闭，$1$ 表示微亮，$2$ 表示全亮。灯的当前档位用一个整数表示。电工师傅说，三档是为了应付不同场合：夜里值班开微亮，检查线路开全亮，平时就关着。

配套的还有 $n$ 个开关，编号也是 $1 \sim n$。这套系统的接线很特别：开关 $j$ 一按下去，灯 $j$ 本身，以及所有与灯 $j$ 有线路相连的灯，档位都会同时加 $1$——已经到 $2$ 的灯会回到 $0$，三档循环。线路图给出了 $m$ 条线路，每条线路连接两盏不同的灯；线路是双向的，开关 $j$ 影响灯 $k$ 时，开关 $k$ 也同样影响灯 $j$。也就是说，按一下某个开关，可能一整片灯跟着变档，噼里啪啦很是热闹。

同一开关可以按任意多次，效果累积；同一个开关按满 $3$ 次，等于白按——受影响的灯每盏加 $3$，各转一圈回到原档。所以真正要考虑的，是每个开关到底按 $0$ 次、$1$ 次还是 $2$ 次。另外，有些接线方案下，可能怎么按都没法让灯全部关闭，电工师傅管那叫"死局"，是设计缺陷，得报修线路而不是接着瞎按。

配电房的记录本上写着每盏灯的初始档位。程老师想知道：从初始状态出发，让 $n$ 盏灯全部关闭，最少一共要按多少次开关？如果办不到，输出 -1。几百个开关摆在那儿，一个一个试显然不现实——光试每种按法，配电房的门怕是都要被按坏了。

输入格式

第一行两个整数 $n, m$，表示灯的数量和线路数量。

第二行 $n$ 个整数 $s_1, s_2, \ldots, s_n$，$s_i \in \{0, 1, 2\}$，表示每盏灯的初始档位。

接下来 $m$ 行，每行两个整数 $u, v$，表示一条连接灯 $u$ 和灯 $v$ 的线路。

输出格式

一行一个整数，表示全部关闭所需的最少总按次；如果办不到，输出 -1。

数据范围

• 特殊性质 A：$m = 0$（没有任何线路，开关 $j$ 只影响灯 $j$）。
• 特殊性质 B：线路构成一条链（灯 $i$ 只与灯 $i-1$、$i+1$ 相连，$m = n - 1$）。
• 对于全部数据，$1 \le n \le 300$，$0 \le m \le \dfrac{n(n-1)}{2}$，$1 \le u, v \le n$，$u \ne v$，无重边。数据保证自由变量不超过 $10$ 个。

样例

样例 1

输入：

3 2
1 2 0
1 2
2 3

输出：

4

解释：开关 $1$ 影响灯 $1, 2$；开关 $2$ 影响灯 $1, 2, 3$；开关 $3$ 影响灯 $2, 3$。一种方案：开关 $1$ 按 $1$ 次、开关 $2$ 按 $1$ 次、开关 $3$ 按 $2$ 次。逐灯核对：灯 $1$ 被按 $2$ 次（$1+2=3$ 转回 $0$）；灯 $2$ 被按 $4$ 次（$2+4=6$ 转回 $0$）；灯 $3$ 被按 $3$ 次（$0+3=3$ 转回 $0$）。总按次 $1+1+2=4$，可以验证不存在更少的方案。

样例 2

输入：

2 1
1 1
1 2

输出：

2

解释：两个开关都同时影响两盏灯。开关 $1$ 按 $2$ 次：两盏灯各加 $2$（$1+2=3$ 转回 $0$），总按次 $2$。也可以两个开关各按 $1$ 次，总按次同样是 $2$——最少就是 $2$。

样例 3

输入：

2 0
1 2

输出：

3

解释：没有线路，开关 $1$ 只管灯 $1$，开关 $2$ 只管灯 $2$。灯 $1$ 要加 $2$ 才回到 $0$，灯 $2$ 要加 $1$，总按次 $2+1=3$。