RedPanda

Undeva într-o pădure din Himalaya, un panda roșu este nevoit să se cațere într-un arbore foarte înalt. Din păcate, acestui panda îi este frică de înălțimi și vă zice că nu are curaj să urce mai sus de nivelul $K$. Astfel, se întreabă dacă l-ați putea ajuta să-și imagineze cum poate face arborele să fie mai puțin înalt.

Se dă descrierea unui arbore cu rădăcină fixă în nodul $1$. Considerăm nivelul rădăcinii ca fiind nivelul $1$, nivelul copiilor săi ca nivelul $2$ și așa mai departe. Arborele poate fi modificat prin următoarea operație în doi pași:

1. Se taie oricare muchie din graf.
2. Se adaugă o nouă muchie în graf.

Cerință

Se cer numărul minim de operații și descrierea acestora pentru a transforma arborele dat într-un arbore unde toate nodurile au nivelul cel mult $K$.

Date de intrare

Pe prima linie a fișierului de intrare redpanda.in se dau $N$, care reprezintă numărul de noduri din arbore, respectiv $K$, care este nivelul maxim dorit. Pe următoarele $N - 1$ linii se regăsesc câte două numere întregi $X$ și $Y$, reprezentând o muchie din arbore între nodurile $X$ și $Y$.

Date de ieșire

Pe prima linie a fișierului de ieșire redpanda.out se află numărul minim de operații $S$. Pe următoarele $S$ linii se vor afla câte patru întregi $A$, $B$, $C$ și $D$, ce descriu operația: se taie muchia dintre $A$ și $B$ și se adaugă muchie între $C$ și $D$.

Operațiile descrise trebuie să respecte următoarele reguli:

• Să nu taie o muchie ce nu există.
• Să nu adauge o muchie deja existentă.
• Să nu adauge o muchie de la un nod la el însuși.
• La final graful rezultat să fie un arbore. După prima operație și până înainte de ultima operație, graful are voie să nu fie arbore.

Restricții și precizări

• $2 \leq N \leq 300 \ 000$
• $1 \leq A, B \leq N$
• $2 \leq K \leq N$

Exemplu

redpanda.in

8 4
1 2
2 3
3 4
4 5
4 6
6 7
7 8

redpanda.out

1
3 4 6 1

Explicație

Tăiem muchia dintre nodurile $3$ și $4$ și adăugăm o nouă muchie intre nodurile $6$ și $1$.