P4796 [BalticOI 2018] Paths

**This problem is translated from [BalticOI 2018](https://boi2018.progolymp.se/tasks/) Day 2 “[Paths](https://boi18-day2-open.kattis.com/problems/boi18.paths)”.** Given an undirected graph with $N$ vertices and $M$ edges. Each vertex has a color. There are $K$ different colors in total, numbered $1 \ldots K$. Find how many simple paths in the graph of length at least $2$ satisfy that all vertices on the path have pairwise distinct colors. Paths with different visiting orders of vertices are considered different paths.

The first line contains three integers $N$, $M$, and $K$. The second line contains $N$ integers between $1$ and $K$, representing the color of each vertex. Each of the next $M$ lines contains two integers $a$ and $b$, denoting an edge of the graph. It is guaranteed that the graph has no self-loops and no multiple edges.

Output one integer: the number of paths in which all vertices have distinct colors. It is guaranteed that the answer will not exceed $10^{18}$.

#### Explanation for Sample 1  The graph in Sample 1 is shown in the figure above. The background color of each vertex is white (color $1$), gray (color $2$), or black (color $3$). There are $10$ paths whose vertices all have distinct colors. They are: ``1-2``, ``2-1``, ``2-3``, ``3-2``, ``2-4``, ``4-2``, ``1-2-4``, ``4-2-1``, ``3-2-4``, and ``4-2-3``. Note that ``1`` cannot be considered a path, because a path must connect at least two vertices. Also, ``1-2-3`` does not satisfy the condition, because two vertices have color $1$. |Subtask|Score|Constraints| |:--:|:--:|:--:| |$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$| Thanks to Hatsune_Miku for providing the translation. Translated by ChatGPT 5