Problem G
Paths

En graf er en matematisk struktur som består av et sett av noder, og et sett av kanter, hvor hver kant forbinder to noder. Et eksempel på en graf med $4$ noder og $3$ kanter er vist i eksempelforklaringen under.

En sti i en graf er definert som en ordnet liste av $2$ eller flere noder, slik at det finnes kanter mellom hvert par av påfølgende noder i listen. I denne oppgaven er vi bare interresert i enkle stier som er de hvor ingen noder opptrer mer enn én gang. Merk at listen er ordnet, så for eksempel representerer “5-6-7”, “5-7-6” og “7-6-5” alle forskjellige stier.

I denne oppgaven er hver node i grafen fargelagt med en av $K$ forskjellige farger. Oppgaven går ut på å finne antall (enkle) stier hvor alle nodene har forskjellige farger.

Input

Første linje i input inneholder tre heltall: $N$ (antall noder), $M$ (antall kanter), og $K$ (antall forskjellige farger).

Andre linje av input inneholder $N$ heltall mellom $1$ og $K$ – fargene på hver av node i grafen (begynnende med node $1$ og sluttende med $N$).

Hver av de neste $M$ linjene beskriver en kant og inneholder to heltall $a, b$ ($1 \le a, b \le N, a \neq b$) – de to nodene som er forbundet med kanten. Det vil være maksimalt én kant mellom ett par av noder.

Output

Skriv ut ett heltall – antall stier hvor alle nodene har forskjellige farger. Dette tallet vil alltid være mindre enn $10^{18}$.

Begrensninger

Løsningen din vil bli testet på et sett av testgrupper, hver verdt et visst antall poeng. Hver testgruppe inneholder et sett av tester. For å få poeng for en testgruppe må du løse alle testene i den gruppen. Din endelige poengsum vil være den høyeste poengsummen du har fått på en enkelt innlevering.

Forklaring av eksempel 1

Grafen i det første eksempelet er vist i figuren, hvor hvert punkt er fylt i enten hvitt (farge 1), grå (farge 2) eller svart (farge 3). Det er 10 stier hvor alle nodene har forskjellige farger: “1-2”, “2-1”, “2-3”, “3-2”, “2-4”, “4-2”, “1-2-4”, “4-2-1”, “3-2-4” og “4-2-3”.

Merk at “1” ikke er godkjent som en sti, fordi den består av bare én node. Ei heller er “1-2-3” lov, fordi den inneholder to noder med farge $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