== include(page="template/taskheader" task_id="colorare3") ==

În Oraşul Simplu au avut loc de curând alegeri pentru funcţia de primar. Cel care a fost ales a câştigat mai ales datorită proiectului său de restaurare a faţadelor tuturor clădirilor, iar acum trebuie să-l pună în practică. Oraşul Simplu constă din $N$ obiective între care există străzi, în aşa fel încât pentru oricare 2 astfel de obiective există un singur drum de a ajunge de la unul la celălalt mergănd pe străzi. Planul primarului constă din colorarea tuturor caselor astfel încât casele de pe aceeaşi stradă să aibă aceeaşi culoare, iar pentru oricare 2 străzi care se întâlnesc în acelaşi obiectiv, culorile să fie diferite. Ştiind ca primarul are la dispoziţie $K$ culori, ar vrea să ştie câte posibilităţi are de a-şi realiza planul de colorare.

În Oraşul Simplu au avut loc de curând alegeri pentru funcţia de primar. Cel care a fost ales a câştigat mai ales datorită proiectului său de restaurare a faţadelor tuturor clădirilor, iar acum trebuie să-l pună în practică. Oraşul Simplu constă din $N$ obiective între care există străzi, în aşa fel încât pentru oricare 2 astfel de obiective există un singur drum de a ajunge de la unul la celălalt mergând pe străzi. Planul primarului constă în colorarea tuturor caselor astfel încât casele de pe aceeaşi stradă să aibă aceeaşi culoare, iar pentru oricare 2 străzi care se întâlnesc în acelaşi obiectiv, culorile să fie diferite. Ştiind ca primarul are la dispoziţie $K$ culori, ar vrea să afle câte posibilităţi sunt de a-şi realiza planul de colorare.

h2. Date de intrare

h2. Exemplu
table(example). |_. colorare3.in |_. colorare3.out |

| TODO
| TODO

| 5 3
1 2
1 3
1 4
3 5
| 12

|
h3. Explicaţie

TODO

Se observă că după ce alegem culorile pentru străzile $(1,2)$, $(1,3)$, $(1,4)$ (având $6$ posibilităţi), strada $(3,5)$ poate fi colorată în $2$ moduri: cu aceeaşi culoare ca $(1,2)$ sau $(1,4)$. Cu mai puţin de $3$ culori nu se poate realiza planul. Aşadar, $6 * 2 = 12$.

== include(page="template/taskfooter" task_id="colorare3") ==

4939