Problem G
Paths

Ein Graph ist ein mathematisches Konstrukt, das aus einer Menge an Knoten und einer Menge an Kanten besteht, die jeweils mit zwei Knoten verbunden sind. Ein Beispiel eines Graphen mit $4$ Knoten und $3$ Kanten ist unten in der Erklärung des Beispiels abgebildet.

Ein Pfad ist definiert als geordnete Liste mit 2 oder mehr Knoten, wobei Kanten zwischen den aufeinanderfolgenden Knoten der Liste existieren. In dieser Aufgabe sind wir nur an einfachen Pfaden interessiert, in denen kein Knoten mehr als einmal vorkommt. Beachte, dass die Liste geordnet ist; z.B. sind “1-2-3”, “1-3-2” und “3-2-1” unterschiedliche Pfade.

In dieser Aufgabe hat jeder Knoten im Graph eine von $K$ Farben. Die Aufgabe ist, die Anzahl der möglichen (einfachen) Pfade zu finden, in denen keine zwei Knoten die gleiche Farbe haben.

Eingabe

Die erste Zeile der Eingabe enthält drei Zahlen: $N$ (die Anzahl der Knoten), $M$ (die Anzahl der Kanten) und $K$ (die Anzahl der verschiedenen Farben).

Die zweite Zeile der Eingabe enthält $N$ Zahlen zwischen $1$ und $K$: die Farben eines jeden Knotens (beginnend mit Knoten $1$ und endend mit Knoten $N$).

Jede der folgenden $M$ Zeilen beschreibt eine Kante und enthält zwei Nummern $a, b$ ($1 \le a, b \le N, a \neq b$): die zwei Knoten, die durch die Kante verbunden werden. Zwischen zwei Knoten gibt es höchstens eine Kante.

Ausgabe

Gib eine Zahl aus: die Anzahl der Pfade, deren Knoten alle unterschiedliche Farben haben. Diese Anzahl wird immer kleiner als $10^{18}$ sein.

Beschränkungen

Deine Lösung wird auf mehreren Testgruppen ausgeführt werden, von denen jede eine bestimmte Punktzahl wert ist. Jede Testgruppe enthält mehrere Testcases. Um Punkte für eine Testgruppe zu bekommen, müssen alle Testfälle in der entsprechenden Gruppe gelöst werden. Deine finale Punktzahl wird die maximal erreichte Punktzahl in einer einzelnen Einsendungen sein.

Beschreibung zu Beispiel 1

Die Abbildung zeigt den Graph des ersten Beispiels, wobei jeder Knoten mit Weiß (Farbe 1), Grau (Farbe 2) oder Schwarz (Farbe 3) gefüllt ist. Es gibt 10 Pfade, deren Knoten alle unterschiedliche Farben haben: “1-2”, “2-1”, “2-3”, “3-2”, “2-4”, “4-2”, “1-2-4”, “4-2-1”, “3-2-4” und “4-2-3”.

Beachte, dass weder “1” ein erlaubter Pfad ist, da es ein einzelner Knoten ist, noch “1-2-3”, da er zwei Knoten der gleichen Farbe enthält.

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