Paths

A graph consists of a set of vertices and a set of edges, each joining two vertices.

A path in the graph is an ordered list of vertices $v_1, v_2, \dots, v_t$ with $t \ge 2$ such that consecutive vertices are joined by an edge. Only simple paths are considered here, so no vertex appears more than once. The order matters: lists containing the same vertices in a different order count as different paths.

Each vertex has one of $K$ colors. Count the simple paths in which no two vertices share a color, so no color appears twice within one path.

The first line contains three integers $N$ (number of vertices), $M$ (number of edges), and $K$ (number of colors), separated by spaces.

The second line contains $N$ integers $c_1, c_2, \dots, c_N$ ($1 \le c_i \le K$), where $c_i$ is the color of vertex $i$.

Each of the next $M$ lines contains two integers $a, b$ ($1 \le a, b \le N$, $a \ne b$), the endpoints of one edge. There is at most one edge between any pair of vertices. The graph may be disconnected.

Print the number of simple paths whose vertices all have distinct colors. Every counted path contains at least two vertices, and two paths that traverse the same vertices in opposite directions are counted separately. The answer is always smaller than $10^{18}$.

Because all colors in a counted path must differ, a path contains at most $K$ vertices. A list with a single vertex is not a path, and any list repeating a color is excluded. The answer fits in a 64-bit signed integer, so print it directly with no modulo.