P4796 [BalticOI 2018] 路径

**题目译自 [BalticOI 2018](https://boi2018.progolymp.se/tasks/) Day2「[Paths](https://boi18-day2-open.kattis.com/problems/boi18.paths)」** 给定一张 $N$ 个点 $M$ 条边的无向图，每个点有一个颜色，所有点的颜色共有 $K$ 种，编号为 $1\ldots K$。求图上有多少条长度至少为 $2$ 的简单路径，满足路径上的每一个点的颜色互不相同。 路径上的点的连接顺序不同看作不同的两条路径。

无

无

#### 样例 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$ 号颜色。 |子任务|分值|数据范围| |:--:|:--:|:--:| |$1$|$23$|$1 \leqslant N,M \leqslant 100, 1 \leqslant K \leqslant 4$| |$2$|$20$|$1 \leqslant N,M \leqslant 300\,000, 1 \leqslant K \leqslant 3$| |$3$|$27$|$1 \leqslant N,M \leqslant 300\,000, 1 \leqslant K \leqslant 4$| |$4$|$30$|$1 \leqslant N,M \leqslant 100\,000, 1 \leqslant K \leqslant 5$| 感谢 Hatsune_Miku 提供的翻译