Problem G
Ścieżki

Graf to struktura matematyczna złożona ze zbioru wierzchołków i zbioru krawędzi, każda krawędź łączy dwa wierzchołki. Przykładowy graf o $4$ wierzchołkach i $3$ krawędziach jest pokazany w wyjaśnieniu pierwszego testu przykładowego.

Ścieżka to ciąg $2$ lub więcej wierzchołków taki, że każde dwa kolejne wierzchołki w ciągu są połączone krawędzią. W tym zadaniu będziemy rozważali prote ścieżki, to jest takie, w których żaden wierzchołek nie występuje więcej niż raz. Kolejność wierzchołków ma znaczenie; przykładowo ,,5-6-7”, ,,5-7-6” and ,,7-6-5” to różne ścieżki.

Każdy wierzchołek ma jeden z $K$ kolorów. Twoim zadaniem jest znalezienie liczby różnych (prostych) ścieżek, na których wszystkie wierzchołki mają różne kolory.

Wejście

Pierwszy wiersz wejścia zawiera trzy liczby całkowite: $N$ (liczbę wierzchołków), $M$ (liczbę krawędzi) i $K$ (liczbę kolorów).

Drugi wiersz wejścia zawiera $N$ liczb całkowitych pomiędzy $1$ a $K$ – kolory wierzchołków (kolejno dla wierzchołków od $1$ do $N$).

Każdy z kolejnych $M$ wierszy opisuje krawędź i zawiera dwie liczby całkowite $a, b$ ($1 \le a, b \le N, a \neq b$) – numery wierzchołków połączonych krawędzią. Między każdą parą wierzchołków będzie co najwyżej jedna krawędź.

Wyjście

Na wyjście wypisz pojedynczą liczbę całkowitą – liczbę ścieżek, na których wszystkie wierzchołki mają parami różne kolory. Wynik nie przekroczy $10^{18}$.

Ograniczenia

Zestaw testów dzieli się na kilka grup, każda jest warta pewną liczbę punktów. Każda grupa składa się z jednego bądź większej liczby testów. Aby otrzymać punkty za daną grupę, Twoje rozwiązanie musi przejść wszystkie testy z tej grupy. Ostateczny wynik za zadanie jest liczony jako maksymalny wynik z pojedynczych zgłoszeń.

Wyjaśnienie do przykładu 1

Rysunek przedstawia graf z pierwszego testu przykładowego, każdy wierzchołek ma kolor biały (kolor 1), szary (kolor 2) lub czarny (kolor 3). Jest 10 ścieżek, na których wszystkie wierzchołki mają różne kolory: ,,1-2”, ,,2-1”, ,,2-3”, ,,3-2”, ,,2-4”, ,,4-2”, ,,1-2-4”, ,,4-2-1”, ,,3-2-4” oraz ,,4-2-3”.

,,1” nie jest poprawną ścieżką, ponieważ zawiera tylko jeden wierzchołek, jak również ,,1-2-3”, ponieważ zawiera dwa wierzchołki o kolorze $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