Fişierul intrare/ieşire:	color2.in, color2.out	Sursă	ONI 2004
Autor	Mugurel Ionut Andreica	Adăugată de
Timp execuţie pe test	0.05 sec	Limită de memorie	65536 kbytes
Scorul tău	N/A	Dificultate	3/5

Vezi solutiile trimise | Statistici

Color2

Ion si Vasile joaca un joc. Ei au la dispozitie un arbore binar strict (adica fiecare nod are 0 sau 2 fii) cu N noduri, numerotate de la 1 la N (nodul numerotat cu 1 este radacina arborelui). Initial, toate nodurile sunt colorate in alb. Jucatorii vor efectua mutari alternativ, iar jucatorul aflat la mutare va colora in negru un nod colorat in alb. Ion efectueaza prima mutare si poate colora in negru orice nod al arborelui. Considerand ca ultimul nod colorat de unul dintre jucatori este P, jucatorul care urmeaza la mutare poate colora in negru unul din urmatoarele noduri (daca nu au fost deja colorate in negru):

• unul din cei doi fii ai lui P (daca P nu este frunza in arbore)
• tatal lui P (daca P nu este radacina arborelui)

Jocul continua pana cand unul dintre jucatori nu mai poate efectua nici o mutare. Atunci, jucatorul care a efectuat ultima mutare este considerat castigator.

Cerinta

Considerand ca ambii jucatori joaca optim, determinati toate nodurile din arbore pe care le poate colora Ion la prima mutare, astfel incat sa fie sigur de victorie.

Date de Intrare

Prima linie a fisierului color2.in contine numarul intreg N, reprezentand numarul de noduri din arbore. Urmatoarele N-1 linii contin cate doua numere intregi separate printr-un spatiu, a si b, avand semnificatia ca a este tatal lui b.

Date de Iesire

Pe prima linie a fisierului color2.out veti afisa numarul intreg M, reprezentand numarul de noduri pe care le poate colora Ion la prima mutare, astfel incat sa fie sigur de victorie. Pe urmatoarea linie veti afisa numerele acestor noduri, in ordine crescatoare.

Restrictii si precizari

• 1 ≤ N ≤ 16 000, N impar

Exemplu

Cum se trimit solutii?