Problem #112

color

Time limit: 0.02s
Memory limit: 64MB
Input: color.in
Output: color.out

Ion şi Vasile joacă un joc. Ei au la dispoziţie un arbore binar strict (adică fiecare nod are 0 sau 2 fii) cu N noduri, numerotate de la 1 la N (nodul numerotat cu 1 este rădăcina arborelui). Iniţial, toate nodurile sunt colorate în alb. Jucătorii vor efectua mutări alternativ, iar jucătorul aflat la mutare va colora în negru un nod colorat în alb. Ion efectuează prima mutare şi poate colora în negru orice nod al arborelui. Considerând că ultimul nod colorat de unul dintre jucători este P, jucătorul care urmează la mutare poate colora în negru unul din următoarele noduri (dacă nu au fost deja colorate în negru) :

  • unul din cei 2 fii ai lui P (dacă P nu este frunză în arbore)
  • tatăl lui P (dacă P nu este rădăcina arborelui)

Jocul continuă până când unul dintre jucători nu mai poate efectua nici o mutare. Atunci, jucătorul care a efectuat ultima mutare este considerat câştigător.

Cerinţă

Considerând că ambii jucători joacă optim, determinaţi toate nodurile din arbore pe care le poate colora Ion la prima mutare, astfel încât să fie sigur de victorie.

Date de intrare

Prima linie a fişierului color.in conţine numărul întreg N, reprezentând numărul de noduri din arbore. Următoarele N-1 linii conţin câte două numere întregi separate printr-un spaţiu, a şi b, având semnificaţia că a este tatăl lui b.

Date de ieşire

Pe prima linie a fişierului color.out veţi afişa numărul întreg M, reprezentând numărul de noduri pe care le poate colora Ion la prima mutare, astfel încât să fie sigur de victorie. Pe următoarea linie veţi afişa numerele acestor noduri, în ordine crescătoare.

Restricţii şi precizări

  • 1 <= N <= 16 000, N impar
  • 40% din teste vor avea N <= 1 000

Exemplu

color.in

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

color.out

6
1 5 6 7 8 9

General info

Uploader: liviu

Author: Mugurel Ionuţ Andreica

Source: ONI 2004 XI-XII: Ziua 1, Problema 1

Submissions