Problem Description

This problem is translated from BalticOI 2018 Day 2 “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.

Input Format

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 Format

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}$.

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

Hint

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$.

Thanks to Hatsune_Miku for providing the translation.

Translated by ChatGPT 5