Problem Description

This problem is a translation of the second day task from BalticOI 2018, titled "Paths"

Given an undirected graph with $N$ vertices and $M$ edges, each vertex has a color, and there are $K$ different colors numbered from $1$ to $K$. Determine how many simple paths of length at least $2$ exist in the graph such that all vertices on each path have distinct colors.

Paths that differ in the order of vertices they connect are considered different.

Input Format

The first line contains three integers $N$, $M$, and $K$.

The second line contains $N$ integers ranging from $1$ to $K$, representing the color of each vertex.

The following $M$ lines each contain two integers $a$ and $b$, representing an edge in the graph.

The graph is guaranteed to have no self-loops or multiple edges.

Output Format

Output a single integer representing the number of paths where all vertices have different colors. The answer is guaranteed to be no more than $10^{18}$.

Sample Input and Output

Sample Input #1

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

Sample Output #1

10

Sample Input #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

Sample Output #2

70

Notes

Sample 1 Explanation

The graph represented in Sample 1 is shown above. Each vertex is colored white (color $1$), gray (color $2$), or black (color $3$). There are $10$ paths where all vertices have different 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 is not considered a path because a path must connect at least two vertices. 1-2-3 is also not valid because it contains two vertices of color $1$.

Thanks to Hatsune_Miku for the translation.

见题面 Input 部分

见题面 Output 部分