Loosely Connected Isolated Nodes

Let us associate each node of a simple undirected graph with some color.
We say that a node v is isolated when the color of v is different from the colors of all immediate neighbours of v.
We say that a pair of nodes {u, v} is a loosely connected isolated pair if both u and v are isolated nodes and the distance between u and v is exactly two.
We remind you that the distance between two nodes is equal to the number of edges in the shortest path connecting these two nodes.

     

Image 1. Three graphs corresponding to Examples 1, 2, and 3 below. Each isolated node is marked by an additional circle. For each of these graphs we give a complete list of losely connected isolated pairs of nodes. a) {0 2}, {2 8}, {2 12}, {7 11}, {7 13}, {8 12}, {8 14}, {11 13}, {12 14}. b) {0 1}, {0 2}, {0 8}, {1 2}, {1 8}, {2 8}, {2 7}, {5 8}, {6 8}, {7 9}. c) {1 3}, {2 6}.

The task

You are given a graph and a color of each its node. Determine the number of loosely connected isolated pairs in the graph.

---

Input

The first input line contains three integers N, E, C separated by space and representing (in this order) the number of nodes in the graph, the number of edges in the graph and the number of node colors in the graph. We assume that the nodes are labeled 0, 1, ..., N−1.
The next line contains N integers, separated by spaces, which represent the list of colors of particular nodes. The colors are listed in ascending order of node labels. The first integer represents the color of node 0, the second integer represents the color of node 1, etc. We assume that the colors are labeled 0, 1, ..., C−1.
Next, there are E text lines, each specifies one edge in the graph. The line contains two integers, separated by space, which represent the labels of the edge endnodes. The edges are listed in no particular order.
It holds, 2 ≤ N ≤ 10⁴, 1 ≤ E ≤ 10⁵, 2 ≤ C ≤ 100.

Output

The output contains one line with one integer denoting the number of loosely connected isolated pairs in the input graph.

Example 1

Input

15 22 3
1 2 0 1 1 0 2 1 2 1 0 1 0 1 0
0 1
1 2
2 3
3 4
5 6
6 7
7 8
8 9
10 11
11 12
12 13
13 14
0 5
1 6
2 7
3 8
4 9
5 10
6 11
7 12
8 13
9 14

Output

9

The graph in Example 1 is depicted in Image 1 a).

Example 2

Input

10 11 4
0 1 2 3 3 1 0 3 1 2
0 3
1 3
2 3
3 4
2 5
4 6
5 7
6 9
7 8
8 9
3 8

Output

10

The graph in Example 2 is depicted in Image 1 b).

Example 3

Input

9 8 2
1 0 0 0 1 1 0 1 1
0 3
1 4
2 5
3 4
4 5
5 6
6 7
4 8

Output

2

The graph in Example 3 is depicted in Image 1 c).

---

Public data

The public data set is intended for easier debugging and approximate program correctness checking. The public data set is stored also in the upload system and each time a student submits a solution it is run on the public dataset and the program output to stdout and stderr is available to him/her.
Link to public data set