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 ai şi bi existente în acel moment în arbore.
* Notează cu V mulţimea vecinilor nodurilor ai şi bi (nodurile care au o muchie directă către cel puţin
unul dintre ai sau bi).
* Şterge din V nodurile ai şi bi, dacă acestea erau prezente.
* Şterge din arbore nodurile ai şi bi, cât şi muchiile care aveau cel puţin un capăt într-unul din
nodurile ai şi bi.
* Adaugă în arbore un nod cu numărul N + i.
* Adaugă muchii între nodul N + i şi fiecare din nodurile din mulţimea V .

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