该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Problem E. Emm, my Milky Tea is Leaking

Input file:　standard input
Output file:　standard output
Time limit:　1 second
Memory limit:　256 megabytes

Ocean 打算请 cls 喝一杯奶茶，于是他买了一杯。现在，他正骑车飞回学校。

我们可以认为 Ocean 位于一个包含 $n$ 个结点（编号 $1$ 到 $n$）$m$ 条边的无向图上 （图不一定连通）。显然 Ocean 可以任意移动，但好景不长——奶茶包装被减速带晃开了！从而事情变得复杂了起来：

移动：Ocean 可以移动到当前所在结点通过一条边相连的相邻结点，但 Ocean 只能移动到 没有奶茶 的结点，不然 Ocean 会滑倒。注意，尽管不能移动到 有奶茶 的结点，但允许 Ocean 从一个当前 有奶茶 的结点出发，移动到相邻 没有奶茶 的结点。

洒落奶茶：Ocean 可以控制骑行的速度，使将要洒出来的奶茶落在指定的当前结点上。换句话说，Ocean 可以控制在哪些结点上洒落奶茶，但是显然 Ocean 需要位于这些结点上才能洒到。奶茶一经洒落就会永久存在于图中，每个结点可以被多次洒落奶茶。

已知 Ocean 所在的无向图初始没有奶茶洒落，Ocean 出现在了地图上的 $S$ 点，并进行了一系列的操作，并最终停留在了 $T$ 点。

现在，给出无向图最终的情况，请你求出有多少种可能的起点终点方案 $(S,T)$，两种方案不同当且仅当它们的起点和终点至少有一个不同。若无合法方案输出 $0$。

Input

第一行包含两个整数 $n,m$ $(1 \leq n \leq 10^5,1 \leq m \leq 2 \times 10^5)$，表示无向图的结点个数和边的个数。

接下来 $m$ 行，每行两个正整数 $u,v$ $(1 \leq u,v \leq n)$，表示 $u,v$ 之间有一条边，可能有 自环或重边。

最后一行包含 $n$ 个正整数，第 $i$ 个正整数 $c_i$ $​(0 \leq c_i \leq 2)$ 表示 $i$ 号结点上最终被洒落了几次奶茶。

Output

输出一行一个正整数，表示题目所求的 $(S,T)$ 的对儿数，若无合法的方案输出 $0$。

Example