Baltic Olympiad in Informatics 2018 Open - day 2

Start

2018-04-29 07:30 UTC

Baltic Olympiad in Informatics 2018 Open - day 2

End

2018-04-29 12:30 UTC
The end is near!
Contest is over.
Not yet started.
Contest is starting in -639 days 22:57:10

Time elapsed

5:00:00

Time remaining

0:00:00

Problem C
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.

Input

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 \neq b$) – vastava servaga ühendatud tippude numbrid. Iga tipupaari vahel on ülimalt üks serv.

Output

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}$.

Constraints

Your solution will be tested on a set of test groups, each worth a number of points. Each test group contains a set of test cases. To get the points for a test group you need to solve all test cases in the test group. Your final score will be the maximum score of a single submission.

Group

Points

Limits

1

23

$1 \le N, M \le 100, 1 \le K \le 4$

2

20

$1 \le N, M \le 300\, 000, 1 \le K \le 3$

3

27

$1 \le N, M \le 300\, 000, 1 \le K \le 4$

4

30

$1 \le N, M \le 100\, 000, 1 \le K \le 5$

Explanation of Sample 1

\includegraphics[width=5cm]{pathsfig.pdf}

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$.

Sample Input 1 Sample Output 1
4 3 3
1 2 1 3
1 2
2 3
4 2
10
Sample Input 2 Sample Output 2
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