图（graph）是一种数学结构，由一组顶点（vertices）和一组连接两个顶点的边（edges）组成。下文的样例解释中展示了一个包含 4 个顶点和 3 条边的图。

图中的路径（path）定义为由 2 个或更多顶点组成的有序列表，使得列表中相邻的顶点之间存在边。在本题中，我们只关注简单路径（simple paths），即路径中没有顶点出现超过一次。注意，该列表是有序的；例如，“5-6-7”、“5-7-6”和“7-6-5”都被视为不同的路径。

在本题中，图中的每个顶点都有 $K$ 种颜色之一。任务是找出所有满足“路径中没有两个顶点颜色相同”的（简单）路径的数量。

输入格式

输入的第一行包含三个整数：$N$（顶点数）、$M$（边数）和 $K$（不同颜色的数量）。

第二行包含 $N$ 个介于 1 和 $K$ 之间的整数，表示每个顶点的颜色（从顶点 1 到顶点 $N$）。

接下来的 $M$ 行，每行描述一条边，包含两个整数 $a, b$（$1 \le a, b \le N, a \neq b$），表示由该边连接的两个顶点。任意两个顶点之间最多只有一条边。

输出格式

输出一个整数，表示所有顶点颜色互不相同的路径数量。该数字始终小于 $10^{18}$。

数据范围

你的解法将在若干测试组上进行测试，每组测试包含若干测试点。为了获得某一组的分数，你需要通过该组内的所有测试点。最终得分为单次提交的最高得分。

说明

第一个样例中的图如上图所示，其中每个顶点已填充为白色（颜色 1）、灰色（颜色 2）或黑色（颜色 3）。共有 10 条顶点颜色互不相同的路径：“1-2”、“2-1”、“2-3”、“3-2”、“2-4”、“4-2”、“1-2-4”、“4-2-1”、“3-2-4”和“4-2-3”。

注意，“1”不被视为路径，因为它只是单个顶点；“1-2-3”也不被视为路径，因为它包含了两个颜色为 1 的节点。

样例

输入 1

4 3 3
1 2 1 3
1 2
2 3
4 2

输出 1

10

输入 2

9 11 4
1 2 3 4 1 2 1 2 2
1 2
1 3
2 3
2 4
3 6
6 2
6 5
4 3
4 5
7 8
9 8

输出 2

70