arborigami

Kaguya, vicepreședintele consiliului de studenți, este răcită. Miyuki vrea, cum este tradițional, să îi ofere cadou o mie de cocori de hârtie. Poate nu o mie... (prea exagerat pentru o simplă răceală), și poate nu cocor... (prea tradițional și oricum nu am hârtie de origami...). Un arbore stea ar trebui să fie ideal!

Miyuki are un arbore (graf conex aciclic) format din N noduri numerotate de la 1 la N. El dorește să îl transforme într-un arbore stea de dimensiune N − K, adică un graf conex aciclic care are cel puțin N − K − 1 frunze (noduri cu exact 1 vecin).

Pentru a transforma arborele său într-un arbore stea, Miyuki va efectua K operații de împăturire a câte două noduri. Pentru a i-a operație de împăturire, Miyuki:

• Alege două noduri distincte $a_i$ și $b_i$ existente în acel moment în arbore.
• Notează cu V mulțimea vecinilor nodurilor $a_i$ și $b_i$ (nodurile care au o muchie directă către cel puțin unul dintre $a_i$ sau $b_i$).
• Șterge din V nodurile $a_i$ și $b_i$, dacă acestea erau prezente.
• Șterge din arbore nodurile $a_i$ și $b_i$, cât și muchiile care aveau cel puțin un capăt într-unul din nodurile $a_i$ și $b_i$
• Adaugă în arbore un nod cu numărul N + i.
• Adaugă muchii între nodul N + i și fiecare din nodurile din mulțimea V .

După o astfel de operație, graful rezultat trebuie să fie în continuare arbore; mai precis, operația efectuată nu trebuie să introducă vreun ciclu. Altfel, operația este invalidă și nu poate fi efectuată.

Deoarece nu vrea să pară că s-a străduit prea mult, Miyuki vrea să facă un număr K minim de operații. Pentru că secretara Chika a promis că nu îl mai învață nimic, trebuie să-l ajutați pe Miyuki să determine:

1. Care este numărul minim K de operații pentru a transforma arborele inițial în arbore stea.
2. Care sunt cele K operații prin care arborele inițial este transformat într-un arbore stea.

Date de intrare

De pe prima linie se va citi un singur număr natural N, reprezentând dimensiunea arborelui inițial. Pe următoarele N − 1 linii vor fi descrise muchiile arborelui inițial, pe linia i + 1 aflându-se două numere naturale $u_i$ și $v_i$, reprezentând nodurile unite de a i-a muchie din arbore.

Date de ieșire

Pe prima linie se va afișa un singur număr natural K, reprezentând numărul minim de operații ce trebuie efectuate. Pe următoarele K linii se vor afișa K perechi de numere naturale $a_i$ și $b_i$ (1 ≤ i ≤ K), separate prin câte un spațiu, reprezentând, în ordine, operațiile de împăturire ce se efectuează asupra arborelui.

Restricţii

• 1 ≤ N ≤ 500 000
• Dacă există mai multe soluții posibile, se poate afișa oricare.
• Dacă se determină corect numărul minim de operații K, dar operațiile afișate nu transformă corect arborele într-unul stea, sau una dintre operații este invalidă conform cu definiția din enunț, se va acorda 30% din punctaj.

Subtask 1 (10 puncte)

• 1 ≤ N ≤ 15

Subtask 2 (20 puncte)

• 1 ≤ N ≤ 200

Subtask 3 (10 puncte)

• $u_i = i, v_i = i + 1$, pentru 1 ≤ i < N

Subtask 4 (60 puncte)

• Nu există alte restricții

Exemple

stdin

5
1 2
2 3
3 4
4 5

stdout

1
2 4

Explicații

Se efectuează o singură operație de împăturire, între nodurile 2 și 4.
Operația decurge în felul următor

• vecinii nodurilor 2 și 4 sunt V = 1, 3, 5
• ștergem nodurile 2 și 4 din arbore
• adăugăm nodul N+1 = 6 și muchiile (1, 6), (3, 6), (5, 6)

Arborele final este cel compus din nodurile 1, 3, 5 și 6 și muchiile (1, 6), (3, 6), (5, 6). Observăm că nodurile 1, 3, și 5 au un singur vecin și doar 6 are 3 vecini, deci arborele rezultat este stea.

stdin

6
1 2
2 3
3 4
4 5
5 6

stdout

2
2 4
5 7

Explicații

Se efectuează două operații de împăturire:

• (2, 4), adăugând nodul N+1 = 7;
• (5, 7), adăugând nodul N+2 = 8.

Arborele final este cel compus din nodurile 1, 3, 6 și 8 și muchiile (1, 8), (3, 8), (6, 8).