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

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

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