Problem G
Vägar

En graf är en matematisk struktur som består av en uppsättning noder, och en uppsättning bågar, där varje båge sammanbinder två noder. Ett exempel på en graf med $4$ noder och $3$ bågar visas i exempelförklaringen nedan.

En väg i grafen definieras som en ordnad lista med $2$ eller fler noder, där det finns en båge mellan den första och andra noden i listan, mellan den andra och tredje, o.s.v. genom hela listan. Vi är bara intresserade av enkla vägar som inte innehåller samma nod flera gånger. Notera att listan är ordnad; exempelvis betraktas “5-6-7”, “5-7-6” och “7-6-5” som olika vägar.

I den här uppgiften har varje nod i grafen en av $K$ färger. Uppgiften är att hitta antalet möjliga (enkla) vägar i vilka alla noder har olika färg.

Indata

Första raden innehåller tre heltal: $N$ (antalet noder), $M$ (antalet bågar), och $K$ (antalet olika färger).

Andra raden innehåller $N$ heltal mellan $1$ och $K$ – färgen på varje nod (första talet beskriver nod nummer $1$ och sista talet nod nummer $N$).

Var och en av de följande $M$ raderna beskriver en båge och innehåller två heltal $a, b$ ($1 \le a, b \le N, a \neq b$) – de två noderna som bågen sammanbinder. Det finns aldrig mer än en båge mellan samma två noder.

Utdata

Skriv ut ett heltal – antalet vägar vars samtliga noder har olika färger. Antalet kommer alltid att vara lägre än $10^{18}$.

Begränsningar

Din lösning kommer att testas på en uppsättning testgrupper, var och en värd en viss poäng. Varje testgrupp innehåller flera testfall. För att få poäng för en testgrupp måste du klara alla testfallen i gruppen. Din slutgiltiga poäng på problemet kommer att vara den maximala poängen av en enda submission.

Förklaring till Exempel 1

Grafen i första exemplet visas i figuren, där varje nod har färgats vit (färg 1), grå (färg 2) eller svart (färg 3). Det finns 10 vägar vars noder har olika färger: “1-2”, “2-1”, “2-3”, “3-2”, “2-4”, “4-2”, “1-2-4”, “4-2-1”, “3-2-4” och “4-2-3”.

Notera att “1” inte är en godkänd väg eftersom det är en ensam nod, och inte heller “1-2-3”, eftersom den innehåller två noder med färg $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