Omizi

În pădurea cu alune exista o mulțime de copaci diferiți. Fiecare copac este special în modul său, dar pe noi ne interesează unul anume. El poate fi reprezentat ca un arbore cu $N$ noduri, dar cu muchii orientate. Omizile sunt insecte foarte draguțe care vă cer ajutorul vostru astăzi. Ele se mișcă prin arbore, dar pot parcurge muchiile doar în sensul orientării lor.
Micul Frate de la MDTV a anunțat că va veni furtuna, așa că omizile trebuie să se ascundă prin nodurile arborelui. Inițial, toate omizile se află într-un singur nod și vor să se împrăștie prin tot arborele. Ele au însă o putere ascunsă, aceea de a inversa orientarea oricărei muchii, dar nu pot face asta de prea multe ori, deoarece încalcă legile de protecție ale copacilor.

Cerință

Omizile sunt, totuși, insecte pretențioase, așă că vă cer să raspundeți la 2 întrebări:

1. Pentru fiecare nod de pornire $i$, aflați numărul minim de muchii care trebuie inversate, astfel încât omizile să poată ajunge din nodul $i$ în oricare alt nod din arbore.
2. Aflați numărul maxim de noduri în care pot omizile să ajungă, începând din nodul $1$, știind că pot inversa maximum $P$ muchii.

Date de intrare

Pe prima linie a fișierului de intrare omizi.in se găsesc $2$ numere întregi, $C$ și $N$, reprezentând cerința care trebuie rezolvată și numărul de noduri din arbore.
Pe următoarele $N - 1$ linii se vor găsi câte $2$ numere $(a, b)$, cu semnificația că există o muchie orientată de la nodul $a$ la nodul $b$.
Dacă $C = 2$, atunci pe ultima linie se găsește un număr întreg $P$, reprezentând numărul maxim de muchii pe care le pot inversa omizile.

Date de ieșire

Dacă $C = 1$, atunci pe prima linie a fișierului de ieșire omizi.out se vor găsi $N$ numere întregi, separate printr-un spațiu, unde al $i$-lea dintre ele reprezintă numărul minim de muchii care trebuie inversate, astfel încât omizile să poată ajunge din nodul $i$ în oricare alt nod.
Dacă $C = 2$, atunci pe prima linie a fișierului de ieșire omizi.out se va găsi un singur număr întreg, reprezentând numărul maxim de noduri în care pot omizile să ajungă din nodul $1$, știind că pot inversa maximum $P$ muchii.

Restricții și precizări

• $1 \leq P < N \leq 700$;
• $1 \leq a, b \leq N$;
• Un arbore cu $N$ noduri și cu muchii orientate este un graf orientat aciclic care, după eliminarea orientării muchiilor, devine un arbore;

  #	Punctaj	Restricții
  0	0	Exemplele
  1	31	$C = 1$
  2	21	$C = 2$, $1 \leq N \leq 20$
  3	11	$C = 2$, $P = 0$
  4	37	Fără restricții suplimentare

Exemplul 1

omizi.in

1 5
1 2
3 2
4 3
5 4

omizi.out

3 4 3 2 1

Explicație

De exemplu, din nodul $2$, trebuie inversate toate cele $4$ muchii pentru a ajunge în celelalte noduri. Din nodul $4$, trebuie inversate doar muchiile $(5, 4)$ și $(1, 2)$.

Exemplul 2

omizi.in

2 5
1 2
3 2
4 3
5 4
2

omizi.out

4

Explicație

Vom inversa muchiile $(3, 2)$ și $(4, 3)$. Astfel, vom putea ajunge din nodul $1$ în nodurile $1, 2, 3, 4$. Oricum am inversa muchiile de maximum $2$ ori, nu putem ajunge și în nodul $5$.