colorare3

Colorare3

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

Poveste şi cerinţă...

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

h2. Date de intrare

Fişierul de intrare $colorare3.in$ ...

Fişierul de intrare $colorare3.in$ conţine pe prima linie numerele $N$ şi $K$. Urmează $N - 1$ linii, fiecare conţinând câte 2 numere $a$ şi $b$ semnificând faptul că există o stradă între obiectivele $a$ şi $b$.

h2. Date de ieşire

În fişierul de ieşire $colorare3.out$ ...

În fişierul de ieşire $colorare3.out$ se va scrie numărul de posibilităţi de colorare modulo $1 000 000 007$.

h2. Restricţii

* $... ≤ ... ≤ ...$

* $1 ≤ N ≤ 100 000$
* $1 ≤ K ≤ 1 000 000 000$
* Obiectivele sunt numerotate de la $1$ la $N$.

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

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| TODO
| TODO

|
h3. Explicaţie

...

TODO

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