Problem G
Teed

Graaf on matemaatiline struktuur, mis koosneb hulgast tippudest ja hulgast servadest, millest igaüks ühendab kaht serva. Allpool on toodud $4$ tipu ja $3$ servaga graafi kirjeldus.

Tee on defineeritud kui $2$ või enam tipuga järjend, kus järjestikuste tippude vahel on servad. Siin ülesandes huvitavad meid ainult lihtsad teed, see tähendab sellised teed, kus ükski tipp ei esine rohkem kui ühe korra. Pane tähele, et järjend on sorteeritud: näiteks järjendid “1-2-3”, “1-3-2” ja “3-2-1” on erinevad teed.

Siin ülesandes on antud graaf, mille iga tipp on värvitud ühega $K$ värvist. Tarvis on leida erinevate teede arv, kus ei leiduks kaht sama värviga värvitud tippu.

Sisend

Sisendi esimesel real on kolm täisarvu: $N$ (tippude arv), $M$ (servade arv) ja $K$ (erinevate värvide arv).

Teisel real on $N$ täisarvu lõigust $1$ kuni $K$, mis tähistavad iga tipu värvi (alustades tipust number $1$ ja lõpetades tipuga number $N$).

Igaüks järgmistest $M$ reast kirjeldab üht serva ja sellel on kaks täisarvu $a,b$ ($1\le a,b\le N,a\ne b$) – vastava servaga ühendatud tippude numbrid. Iga tipupaari vahel on ülimalt üks serv.

Väljund

Väljastada üks täisarv: erinevate teede arv, kus sama tee raames on kõik tipud eri värvi. Vastus on alati väiksem kui ${10}^{18}$.

Piirangud

Selles ülesandes on testid jagatud gruppidesse. Iga grupi eest saavad punkte ainult need programmid, mis lahendavad õigesti kõik gruppi kuuluvad testid. Sinu lõplik skoor on esitatud lahenduste skooride maksimum.

Näite 1 selgitus

Esimeses näites kirjeldatud graaf on toodud joonisel, kus iga tipp on kas valge (värv 1), hall (värv 2) või must (värv 3). Graafis leidub 10 teed, mille kõik tipud on erinevat värvi: “1-2”, “2-1”, “2-3”, “3-2”, “2-4”, “4-2”, “1-2-4”, “4-2-1”, “3-2-4” ja “4-2-3”.

Pane tähele, et “1” ei ole tee, sest seal on ainult üks tipp, ning “1-2-3” ei ole lubatud tee, sest selles on kaks tippu värviga $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