题目描述

题目译自 BalticOI 2018 Day2「Paths」

给定一张 $N$ 个点 $M$ 条边的无向图，每个点有一个颜色，所有点的颜色共有 $K$ 种，编号为 $1\ldots K$。求图上有多少条长度至少为 $2$ 的简单路径，满足路径上的每一个点的颜色互不相同。

路径上的点的连接顺序不同看作不同的两条路径。

输入格式

第一行包含三个整数 $N$, $M$ 和 $K$。

第二行包含 $N$ 个在 $1$ 到 $K$ 之间的整数，表示每个点的颜色。

接下来的 $M$ 行每行两个整数 $a$ 和 $b$，表示图的一条边。

数据保证图无自环无重边。

输出格式

输出一个整数表示每一个点颜色都不同的路径条数。保证答案不会超过 $10^{18}$。

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

10

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

70

提示

样例 1 解释

样例 1 中表达的图如上图所示。每个点的底色分别为白色（颜色 $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$ 号颜色。

感谢 Hatsune_Miku 提供的翻译