Paths

A *graph* is a mathematical structure which consists
of a set of *vertices*, and a set of *edges*,
each connecting two vertices. An example of a graph with
$4$ vertices and
$3$ edges is shown in the
sample explanation below.

A *path* in the graph is defined as an ordered list
of $2$ or more vertices,
such that there are edges between consecutive vertices in the
list. In this task we are only interested in *simple
paths* in which no vertex occurs more than once. Note that
the list is ordered; for example, “`5-6-7`”, “`5-7-6`” and
“`7-6-5`” are all treated as different
paths.

In this task, each vertex in the graph has one of $K$ colors. The task is to find the number of possible (simple) paths in which no two vertices have the same color.

The first line of input contains three integers: $N$ (the number of vertices), $M$ (the number of edges), and $K$ (the number of different colors).

The second line of input contains $N$ integers between $1$ and $K$ – the colors of each vertex (starting with vertex $1$ and ending with vertex $N$).

Each of the following $M$ lines describes an edge and contains two integers $a, b$ ($1 \le a, b \le N, a \neq b$) – the two vertices connected by the edge. There will be at most one edge between any two vertices.

Output one integer – the number of paths whose vertices all have distinct colors. This number will always be smaller than $10^{18}$.

Your solution will be tested on a set of test groups, each worth a number of points. Each test group contains a set of test cases. To get the points for a test group you need to solve all test cases in the test group. Your final score will be the maximum score of a single submission.

Group |
Points |
Limits |

1 |
23 |
$1 \le N, M \le 100, 1 \le K \le 4$ |

2 |
20 |
$1 \le N, M \le 300\, 000, 1 \le K \le 3$ |

3 |
27 |
$1 \le N, M \le 300\, 000, 1 \le K \le 4$ |

4 |
30 |
$1 \le N, M \le 100\, 000, 1 \le K \le 5$ |

The graph in the first example is illustrated in the figure,
where each vertex has been filled with white (color 1), gray
(color 2) or black (color 3). There are 10 paths whose vertices
all have distinct colors: “`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 allowed as a
path, because it is a single vertex, nor is “`1-2-3`”, because it contains two nodes of color
$1$.

Sample Input 1 | Sample Output 1 |
---|---|

4 3 3 1 2 1 3 1 2 2 3 4 2 |
10 |

Sample Input 2 | Sample Output 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 |
70 |