Paths

This problem is translated from BalticOI 2018 Day2 problem "Paths".

You are given an undirected graph with \(N\) vertices and \(M\) edges. Each vertex is assigned a color. There are in total \(K\) different colors, labeled from 1 to \(K\). A simple path is a sequence of vertices where every two consecutive vertices are connected by an edge and no vertex appears more than once.

Your task is to count the number of simple paths of length at least 2 (i.e. containing at least two vertices) such that all vertices on the path have distinct colors. Note that the same set of vertices visited in a different order is considered a different path.

Note on format: If an expression must be shown in LaTeX format, enclose it within \( ... \) or \[ ... \]. For example, the number of vertices is given by \(N\) and colors range from \(1\) to \(K\).

inputFormat

The input consists of the following:

• The first line contains three integers \(N\), \(M\), and \(K\), representing the number of vertices, number of edges, and the number of different colors respectively.
• The second line contains \(N\) integers, where the \(i\)-th integer represents the color of vertex \(i\).
• Each of the following \(M\) lines contains two integers \(u\) and \(v\), indicating there is an undirected edge between vertex \(u\) and vertex \(v\).

It is guaranteed that \(1 \leq u, v \leq N\) and all numbers are separated by spaces.

outputFormat

Output a single integer: the number of simple paths (of length at least 2) in the graph where no two vertices on the path share the same color.

sample

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

5