NézetNyomtat

Banda
Címkék > Feladat

Banda

Egy banda hierarchikusan épül fel, minden tagjának legfeljebb K közvetlen beosztottja lehet. Az üzenetek egy tagtól a beosztottjáig pontosan 1 nap alatt érnek el. Az a cél, hogy a főnök (aki már senki másnak nem beosztottja) üzenetei a lehető leghamarabb érjenek el minden bandataghoz. Ennek érdekében egyetlen egy bandatag főnökét meg szabad változtatni, természetesen úgy, hogy továbbra se legyen senkinek K-nál több közvetlen beosztottja. Az áthelyezett tag persze a beosztottjait is viszi magával.

Feladat

Írj programot, amely megadja, hogy melyik bandatag főnökét változtassuk meg, és ki legyen az új főnöke!

Bemenet

A banda.be szöveges állomány első sorában két egész szám van, a bandatagok száma (1$\le$N$\le$1000), valamint az egy taghoz tartozó közvetlen beosztottak maximális száma (2$\le$K$\le$10). A további N-1 sor mindegyike egy U V egész számpárt tartalmaz; ami azt jelenti, hogy az U bandatag főnöke a V bandatagnak. Teljesül, hogy 1$\le$U$\le$V$\le$N. A banda főnöke az 1-es sorszámú tag.

Kimenet

A banda.ki szöveges állomány egyetlen sorába az áthelyezendő bandatag sorszámát és az új főnöke sorszámát kell írni, egyetlen szóközzel elválasztva! Ha nincs áthelyezendő bandatag, akkor két 0 kerüljön az eredménybe! Több megoldás esetén bármelyik megadható.

Példa

banda.bebanda.ki
15 3 1 9 1 10 1 11 9 5 9 6 9 8 8 7 8 13 7 14 7 15 11 2 11 3 11 4 10 12 7 10

Tesztadatok