Problem D
Пути

Граф – это структура, состоящая из множества вершин, и множества ребер. Каждое ребро соединяет две вершины. На иллюстрации ниже показан пример графа с $4$ вершинами и $3$ ребрами.

Путь в графе – это последовательность из $2$ или более вершин, соединённых последовательно рёбрами. Обратите внимание, что порядок вершин играет роль. Например, “5-6-7”, “5-7-6” и “7-6-5” – это разные пути.

В данной задаче каждая вершина графа раскрашена в один из $K$ цветов. Задача состоит в том, чтобы найти количество возможных путей, в которых никакие две вершины не имеют один и тот же цвет.

Ввод

На первой строке даны три целых числа: $N$ (число вершин), $M$ (число рёбер), и $K$ (число различных цветов).

На второй строке даны $N$ целых чисел между $1$ и $K$ – цвета каждой вершины (начиная с $1$ до $N$).

Каждая из следующих $M$ строк описывает одно ребро, и содержит два целых числа $a, b$ ($1 \le a, b \le N, a \neq b$) – две вершины, соединённых соответствующим ребром. Две вершины не могут быть соединены более чем одним ребром.

Вывод

Выведите одно целое число – количество различных путей, все вершины которых имеют разные цвета. Известно, что ответ не превышает $10^{18}$.

Ограничения

Тесты разделены на группы. Очки за группу даются только если корректно решены все тесты в группе.

Объяснение примера 1

Граф в первом примере проиллюстрирован на рисунке выше, где каждая вершина раскрашена в белый (цвет 1), серый (цвет 2) или чёрный (цвет 3). Всего есть 10 путей, в которых все вершины имеют различные цвета: “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”.

Обратите внимание, что “1” не считается подходящим путём, т.к. это всего лишь одна вершина. Не подходит и путь “1-2-3”, т.к. содержит две вершины цвета $1$.

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

10

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

70