arbore

Se da un arbore format din n noduri în care fiecare nod are asociat un numar natural nenul.

Cerinta

Sa se selecteze din arborele initial un subgraf conex pentru care suma valorilor asociate nodurilor este egala cu un numar natural k dat. Un subgraf se obtine eliminand din graful dat noduri împreuna cu muchiile incidente cu acestea.

Nodurile arborelui sunt numerotate de la 1 la n, radacina fiind nodul numerotat cu 1.

Fisierul de intrare arbore.in are urmatoarea structura:
- pe prima linie sunt scrise numerele n si k, separate printr-un spatiu;
- pe cea de-a doua linie este scrisa valoarea asociata nodului 1 (radacina arborelui);
- pe cea de-a treia linie sunt scrise doua numere, primul reprezentând nodul parinte al nodului 2, iar al doilea reprezentând valoarea asociata nodului 2;
- pe cea de-a patra linie sunt scrise doua numere, primul reprezentând nodul parinte al nodului 3, iar al doilea reprezentând valoarea asociata nodului 3;
...
- pe linia n+1 sunt scrise doua numere, primul reprezentând nodul parinte al nodului n, iar al doilea reprezentând valoarea asociata nodului n.

Fisierul arbore.out va contine o linie cu numarul -1 (daca nu exista solutie) sau, daca exista solutie, se vor afisa nodurile ce formeaza un subgraf conex care respecta cerinta problemei (câte un singur nod pe fiecare linie).

Restrictii

1 <= n <= 100
1 <= k <= 1000

1 <= valoarea asociata unui nod <= 1000
Solutia nu este unica.

Exemplu

arbore.in	arbore.out
10 29 30 1 7 1 22 2 5 2 10 4 1 4 2 5 25 5 2 5 4	2 4 5 6 9 10

Timp maxim de executie pe test: 0.3 secunde