경로

정점들의 집합과, 두 정점을 잇는 간선들의 집합으로 이루어진 구조를 그래프라고 한다.

그래프의 경로는 정점들의 순서열 $v_1, v_2, \dots, v_t$ ($t \ge 2$) 로, 연속한 두 정점 사이에는 항상 간선이 있어야 한다. 이 문제에서는 어떤 정점도 두 번 이상 등장하지 않는 단순 경로만 생각한다. 순서열은 순서를 구분하므로, 같은 정점들로 이루어져 있어도 순서가 다르면 서로 다른 경로로 센다.

각 정점에는 $1$부터 $K$까지의 색 중 하나가 칠해져 있다. 하나의 경로 안에 같은 색의 정점이 두 번 나타나지 않는 단순 경로가 몇 개인지 구하라.

첫째 줄에 세 정수 $N$ (정점의 수), $M$ (간선의 수), $K$ (색의 수)가 공백으로 구분되어 주어진다.

둘째 줄에 $N$개의 정수 $c_1, c_2, \dots, c_N$ ($1 \le c_i \le K$)이 주어진다. $c_i$는 정점 $i$의 색이다.

이어지는 $M$개의 줄에는 각 간선의 양 끝점 $a, b$ ($1 \le a, b \le N$, $a \ne b$)가 주어진다. 어떤 두 정점 사이에도 간선은 최대 하나이다. 그래프는 연결 그래프가 아닐 수 있다.

색이 서로 모두 다른 단순 경로의 개수를 한 줄에 출력하라. 세는 경로는 정점을 2개 이상 포함해야 하며, 같은 정점들을 반대 방향으로 지나는 경로는 서로 다르게 센다. 답은 항상 $10^{18}$보다 작다.

모든 색이 달라야 하므로 하나의 경로가 포함할 수 있는 정점은 최대 $K$개이다. 정점이 하나뿐인 목록은 경로가 아니며, 같은 색이 두 번 등장하는 순서열도 세지 않는다. 답은 64비트 정수 범위에 들어가므로 나머지 연산 없이 그대로 출력하면 된다.