Problem D
Keliai

Grafas – matematinė struktūra, sudaryta iš viršūnių ir briaunų aibių, kur kiekviena briauna jungia dvi viršūnes. Grafo su $4$ viršūnėmis ir $3$ briaunomis pavyzdys pateiktas pavyzdinio testo paaiškinime.

Kelias apibrėžiamas kaip surikiuota $2$ ar daugiau viršūnių seka, tokia, kad bet kurias dvi gretimas sąrašo viršūnes jungia briauna. Šiame uždavinyje mus domina tik $paprastieji$ keliai, kuriuose jokia viršūnė nepasikartoja daugiau nei vieną kartą. Atkreipkite dėmesį, kad viršūnių tvarka kelyje yra svarbi – pavyzdžiui, “5-6-7”, “5-7-6” ir “7-6-5” yra laikomi skirtingais keliais.

Šiame uždavinyje kiekviena grafo viršūnė yra vienos iš galimų $K$ spalvų. Kiek yra tokių galimų (paprastųjų) kelių, kad visos konkrečiam keliui priklausančios viršūnės būtų skirtingų spalvų?

Pradiniai duomenys

Pirmoje eilutėje pateikiami trys sveikieji skaičiai: $N$ (viršūnių skaičius), $M$ (briaunų skaičius) ir $K$ (skirtingų spalvų skaičius).

Antroje eilutėje yra $N$ sveikųjų skaičių iš intervalo nuo $1$ iki $K$ – visų viršūnių spalvos (pradedant $1$-ąja viršūne ir baigiant $N$-ąja).

Tolimesnės $M$ eilučių nusako po briauną – kiekvienoje pateikiama po du sveikuosius skaičius $a, b$ ($1 \le a, b \le N, a \neq b$) – dvi briauna sujungtas viršūnes. Tarp bet kurių dviejų viršūnių bus ne daugiau nei viena briauna.

Rezultatai

Išveskite vieną sveikąjį skaičių – skaičių kelių, kurių visos viršūnės yra skirtingų spalvų. Šis skaičius visada bus mažesnis nei $10^{18}$.

Ribojimai

Jūsų sprendimas bus testuojamas su keliomis testų grupėmis, kiekviena kurių vertinama tam tikru skaičiumi taškų. Kiekvieną testų grupę sudarys keletas testų. Taškai už testų grupę skiriami tik jei įveikiate visus tos grupės testus.

Pirmojo pavyzdžio paaiškinimas

Pirmojo sąlygos testo grafas pavaizduotas paveikslėlyje, kur visos viršūnės nuspalvintos baltai (spalva 1), pilkai (spalva 2) arba juodai (spalva 3). Yra 10 kelių, kuriuose visos viršūnės skirtingų spalvų: “1-2”, “2-1”, “2-3”, “3-2”, “2-4”, “4-2”, “1-2-4”, “4-2-1”, “3-2-4” ir “4-2-3”.

Atkreipkite dėmesį, kad “1” nėra laikomas keliu, nes jame tik viena viršūnė, bei “1-2-3” neatitinka reikalavimų, nes turi dvi tos pčios spalvos ($1$) viršūnes.

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