Baltic Olympiad in Informatics: 2018 Day 2, Problem 3

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.

Input

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

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

Constraints

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~

Explanation of Sample 1

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

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