arbore

Se dă un arbore format din $n$ noduri numerotate de la $1$ la $n$. Rădăcina este nodul numerotat cu $1$ și fiecare nod are asociat un număr natural nenul.

Cerință

Să se selecteze din arborele iniţial un subgraf conex pentru care suma valorilor asociate nodurilor este egală cu un număr natural $k$ dat. Un subgraf este graful din care se elimină noduri împreună cu muchiile aferente.

Date de intrare

Fişierul de intrare arbore.in, are următoarea structură:

• pe prima linie sunt scrise numerele $n$ şi $k$;
• pe cea de-a doua linie este scrisă valoarea asociată nodului $1$ (rădăcina arborelui);
• pe cea de-a treia linie sunt scrise două numere, primul reprezentând nodul părinte al nodului $2$, iar al doilea reprezentând valoarea asociată nodului $2$;
• pe cea de-a patra linie sunt scrise două numere, primul reprezentând nodul părinte al nodului $3$, iar al doilea reprezentând valoarea asociată nodului $3$;
• ...
• pe linia $n+1$ sunt scrise două numere, primul reprezentând nodul părinte al nodului $n$, iar al doilea reprezentând valoarea asociată nodului $n$.

Date de ieşire

Ieşirea se va face în fişierul arbore.out:

• dacă nu există soluţie se va afişa doar numărul $-1$ pe prima linie;
• dacă există soluţie se vor afişa nodurile ce formează un subgraf conex care respectă cerinţa problemei (câte un singur nod pe fiecare linie).

Restricţii și precizări

• $1 \le n \le 100$
• $1 \le k \le 1\ 000$
• Valoarea asociată unui nod este un număr din intervalul $[1, 1\ 000]$.

Exemplu

arbore.in

10 29
30
1 7
1 22
2 5
2 10
4 1
4 2
5 25
5 2
5 4

arbore.out

2
4
5
6
9
10

Explicație