Problem G
Ceļi

Grafs ir matemātisks objekts, kas sastāv no virsotnēm un šķautnēm, kas katra savieno divas virsotnes. Piemērs grafam ar $4$ virsotnēm un $3$ šķautnēm ir parādīts zemāk.

Ceļš tiek definēts kā secīga virkne no $2$ vai vairāk virsotnēm, tāda, ka starp blakus virsotnēm virknē pastāv šķautne. Šajā uzdevumā mūs interesē tikai vienkāršie ceļi, kuros neviena virsotne neparādās vairāk kā vienu reizi. Ievērojiet, ka secība ir svarīga; piemēram, “5-6-7”, “5-7-6” un “7-6-5” tiek visi uzskatīti par dažādiem ceļiem.

Šajā uzdevumā katra grafa virsotne ir vienā no $K$ krāsām. Uzdevums ir atrast (vienkāršo) ceļu skaitu, kas nesatur virsotnes vienādās krāsās.

Ievaddati

Pirmā ievada rinda satur trīs veselus skaitļus: $N$ (virsotņu skaits), $M$ (šķautņu skaits) un $K$ (dažādu krāsu skaits).

Otrā ievada rinda satur $N$ skaitļus starp $1$ un $K$ — katras virsotnes krāsu (sākot ar virsotni $1$ un beidzot ar virsotni $N$).

Katra no sekojošajām $M$ rindām apraksta šķautni un satur divus veselus skaitļus $a, b$ ($1 \le a, b \le N, a \neq b$) — divas virsotnes, kuras savieno šķautne. Starp katrām divām virsotnēm būs ne vairāk kā viena šķautne.

Izvaddati

Izvadiet vienu veselu skaitli — ceļu skaitu, kuros visas virsotnes ir dažādās krāsās. Šis skaitlis vienmēr būs mazāks par $10^{18}$.

Ierobežojumi

Jūsu risinājums tiks testēts uz vairākām testu grupām, par katru no tām var iegūt punktus. Katra testu grupa satur vienu vai vairākus testus. Lai iegūtu punktus par testu grupu, jums ir pareizi jāatrisina visi testi šajā grupā. Jūsu beigu vērtējums par uzdevumu būs starp visiem iesūtījumiem lielākais.

1. parauga paskaidrojums

Attēlā parādīts pirmā piemēra grafs, kur katra virsotne ir iezīmēta balta (krāsa 1), pelēka (krāsa 2) vai melna (krāsa 3). Pastāv 10 ceļi, kuros visas virsotnes ir dažādās krāsās: “1-2”, “2-1”, “2-3”, “3-2”, “2-4”, “4-2”, “1-2-4”, “4-2-1”, “3-2-4” un “4-2-3”.

Ievērojiet, ka “1” neskaitās kā ceļš, jo tā ir viena virsotne, kā arī neskaitās “1-2-3”, jo tas satur divas virsotnes krāsā $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