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

!https://infoarena.ro/problema/arborigami?action=download&file=unknown.png&safe_only=false!

!>problema/arborigami?unknown.png!

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!

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 <tex> ${a}_{i}$ </tex> şi <tex> ${b}_{i}$ </tex> existente în acel moment în arbore.
* Notează cu $V$ mulţimea vecinilor nodurilor <tex> ${a}_{i}$ </tex> şi <tex> ${b}_{i}$ </tex> (nodurile care au o muchie directă către cel puţin unul dintre <tex> ${a}_{i}$ </tex> sau <tex> ${b}_{i}$ </tex>).
* Şterge din $V$ nodurile <tex> ${a}_{i}$ </tex> şi <tex> ${b}_{i}$ </tex>, dacă acestea erau prezente.
* Şterge din arbore nodurile <tex> ${a}_{i}$ </tex> şi <tex> ${b}_{i}$ </tex>, cât şi muchiile care aveau cel puţin un capăt într-unul din nodurile <tex> ${a}_{i}$ </tex> şi <tex> ${b}_{i}$ </tex>.

* 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$.

h2. 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 <tex> ${u}_{i}$ </tex> şi <tex> ${v}_{i}$ </tex>, reprezentând nodurile unite de a $i$-a muchie din arbore.

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.

h2. 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 <tex> ${a}_{i}$ </tex> şi <tex> ${b}_{i}$ </tex> ({$1 &le; i &le; K$}), separate prin câte un spaţiu, reprezentând, în ordine, operaţiile de împăturire ce se efectuează asupra arborelui.

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.

h2. Restricţii

$60$
| $1 ≤ N ≤ 15$
$1 ≤ N ≤ 200$

<tex> ${u}_{i} = i, {v}_{i} = i + 1$</tex> pentru $1 &le; i &lt; N$.

$u{~i~} = i, v{~i~} = i + 1$ pentru $1 ≤ i < N$.

Nu există alte restricţii.
|