Ranuto are un program de antrenament de-a lungul a mai multor zile, în care vrea să învețe o nouă tehnică: “11th Gate Super Convincing Chakra Dual-Core Rasengan”. Din motive obiective, vrea să știe din avans în ce ar putea consta antrenamentul lui într-o zi anume (vine Kasura să se uite la el).

Se dă un arbore cu N noduri, numerotate de la 1 la N. Arborele este înrădăcinat în nodul 1. Vrem să facem o parcurgere a arborelui, pornind din rădăcină. Pentru fiecare nod, putem considera fiii acestuia în orice ordine dorim. Există două tipuri de cerințe, reprezentate printr-un număr c:

• Pentru C = 1, parcurgerea va fi de tip adâncime (DFS) pre-ordine.
• Pentru C = 2, parcurgerea arborelui va fi de tip lățime (BFS).

Pseudocodul pentru parcurgeri poate fi consultat mai jos:

Algoritmul 1. Parcurgere în adâncime (DFS) pre-ordine
p ← listă vidă (va conține nodurile din parcurgere)
procedură DFS(arbore, nod):
    adaugă nod în spatele lui p
    pentru fiecare fiu x al lui nod:
        DFS(arbore, x)
DFS(arbore, 1)

Algoritmul 2. Parcurgere în lățime (BFS)
p ← listă vidă (va conține nodurile din parcurgere)
procedură BFS(arbore):
    q ← coadă vidă
    adaugă nodul 1 în spatele lui q
    cât timp q nu este vidă:
        f ← nodul din fața lui q
        scoate f din fața lui q
        adaugă f în spatele lui p
        pentru fiecare fiu x al lui f:
            adaugă nodul x în spatele lui q
BFS(arbore)

Cerința

Care noduri din arbore pot să fie pe a K-a poziție în vreuna dintre posibilele parcurgeri?

Date de intrare

Pe prima linie a fișierului keidei.in se găsesc trei numere, C, N și K. Pe următoarele N-1 linii se găsesc câte 2 numere, A și B, semnificând existența unei muchii în arbore între nodurile A și B.

Date de ieșire

Afișaţi în fișierul keidei.out pe o linie, cu un spaţiu între ele, în ordine crescătoare, toate nodurile care pot fi pe a K-a poziție în vreo parcurgere de tipul stabilit de C. Nu trebuie afișat numărul de noduri.

Restricții și precizări

• 1 ≤ N ≤ 10.000
• 1 ≤ K ≤ N
• Pentru 5 puncte, C = 1, N ≤ 10
• Pentru 5 puncte, C = 2, N ≤ 10
• Pentru 5 puncte, C = 1, arborele este binar complet, cu N de forma 2p - 1, p număr natural nenul.
• Pentru 5 puncte, C = 2, arborele este binar complet, cu N de forma 2p - 1, p număr natural nenul.
• Pentru 20 puncte, C = 1, N ≤ 500
• Pentru 20 puncte, C = 2, N ≤ 500
• Pentru 15 puncte, C = 1, N ≤ 3.500
• Pentru 10 puncte, C = 2, N ≤ 5.000
• Pentru 15 puncte, C = 1, N ≤ 10.000

Exemplul 1:

keidei.in

1 8 5
1 2
1 3
1 4
2 5
2 6
3 7
5 8

keidei.out

2 5 6 8

Explicație

Pentru că putem să considerăm fiii oricărui nod din arbore în ce ordine dorim, putem să presupunem că parcurgerea noastră în adâncime parcurge fiii unui nod de la stânga la dreapta după ce stabilim ordinea.

Putem verifica orice alt aranjament pentru a garanta că orice alt nod în afară de 2, 5, 6, 8 nu poate fi pe a 5-a poziție într-o parcurgere în adâncime preordine.

Exemplul 2:

keidei.in

1 17 15
1 2
1 3
1 4
2 5
3 6
3 7
4 8
5 9
5 10
8 11
8 12
8 13
8 14
9 15
10 16
10 17

keidei.out

3 10 11 12 13 14 16 17

Exemplul 3:

keidei.in

2 8 5
1 2
1 3
2 4
2 5
2 7
2 8
3 6

keidei.out

4 5 7 8

Explicație

Putem observa că oricum am aranja arborele, primele 3 noduri din parcurgere vor fi ori 1, 2, 3, ori 1, 3, 2. Dacă 2 este înaintea lui 3 în parcurgere, atunci 6 va fi neapărat ultimul nod din parcurgere. Dacă 3 ar fi înaintea lui 2, atunci 6 va fi neapărat pe a patra poziție în parcurgere. Astfel, singurele noduri care pot fi pe a 5-a poziție sunt 4, 5, 7, 8.