Problem E
Leiðir

Net er stærðfræðilegt mynstur sem er samansett af mengi hnúta og mengi leggja, þar sem hver leggur tengir tvo hnúta. Dæmi um net með $4$ hnútum og $3$ leggjum er sýnt í útskýringu sýnidæma að neðan.

Leið i neti er skilgreint sem raðaður listi af $2$ eða fleiri hnútum, þannig að það sé leggur milli samliggjandi hnúta í listanum. Í þessu verkefni höfum við aðeins áhuga á einföldum leiðum þar sem enginn hnútur kemur fyrir oftar en einu sinni. Taktu eftir að listinn er raðaður, til dæmis, “5-6-7”, “5-7-6” og “7-6-5” eru mismunandi leiðir.

Í þessu verkefni er hver hnútur í netinu litaður með einum a $K$ litum. Verkefnið er að finna fjölda mögulegra (einfaldra) leiða þar sem engir tveir hnútar eru litaðir eins.

Inntak

Fyrsta línan af inntakinu inniheldur þrjár heiltöllur: $N$ (fjöldi hnúta), $M$ (fjöldi leggja), og $K$ (fjöldi mismunandi lita).

Önnur línan af inntakinu inniheldur $N$ heiltölur á milli $1$ og $K$ – litirnir á hverjum hnút (byrjar á hnút $1$ og endar á hnút $N$).

Næst koma $M$ línur, hver og ein þeirra lýsir legg og inniheldur tvær heiltölur $a,b$ ($1\le a,b\le N,a\ne b$) – hnútarnir tveir eru tengdir með leggnum. Fyrir hverja tvo hnúta er mesta lagi einn leggur á milli þeirra.

Úttak

Skrifaðu út eina heiltölu – fjölda leiða þar sem allir hnútarnir hafa mismunandi liti. Þessi tala verður alltaf minni en ${10}^{18}$.

Takmarkanir

Lausnin þín verður prófuð á einhvern fjölda prufuhópa, hver hópur gefur einhvern fjölda stiga. Hver hópur inniheldur einhvern fjölda prufutilvika. Til að fá stig fyrir hóp þarftu að leysa öll prufutilvik innan hópsins. Lokastigin eru fengin úr skilunum sem gáfu hæst stig.

Útskýring á sýnidæmi 1

Netið í fyrsta sýnidæminu er sýnt á myndinni, þar sem hver hnútur hefur verið litaður með hvítum (litur 1) , gráum (litur 2) eða svörtum (litur 3) lit. Það eru 10 leiðir þar sem allir hnútarnir hafa mismunandi liti: “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”.

Taktu eftir að “1” er ekki leyft sem leið, því það er aðeins einn hnútur. “1-2-3” er einnig ekki leyft því það inniheldur tvær nóður með lit $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