1                                                                                                                    Baraj Bucuresti septembrie 1997
Ziua 1 - Problema 1
   Activ-Inactiv

   Se considera un arbore oarecare avand n noduri, n<=200. Nodurile arborelui se impart in 2 categorii : active si inactive. Initial toate nodurile sunt inactive. In acest arbore, deplasarea de la nodul i la nodul j este posibila doar daca sunt indeplinite urmatoarele conditii :
   - nodul j este ascendent sau descendent direct al lui i(tata sau fiu);
   - nodul j este inactiv;
  - dupa atingerea nodului j, va fi selectat unul din fiii inactivi ai sai si va fi activat, impreuna cu subarborele care il are pe acest fiu drept radacina.Daca j nu are fii inactivi nu se va activa nimic.
   Se considera ca nod de plecare o frunza (nod terminal in arbore). Definim lungimea unui drum (parcurs in conditiile de mai sus) ca fiind numarul de muchii traversate. 
    Se cere sa se produca, pornind din nodul de plecare, un drum de lungime maxima.
   
    Datele de intrare se citesc din fisierul INPUT.TXT, cu urmatorul format :
   - pe prima linie n, numarul de noduri;
   - pe urmatoarele n-1 linii, perechi de numere (i,j) cu semnificatia : i este fiu al lui j;
   - pe urmatoarea linie nodul de plecare;
   
    Iesirea se va face in fisierul OUTPUT.TXT, care va avea urmatorul format :
    - pe prima linie lungimea drumului maxim;
  - pe a doua linie nodurile drumului(in ordinea aparitiei pe drum), exceptand nodul de plecare;
   - pe urmatoarea linie, pentru fiecare nod din drumul afisat pe linia anterioara, se va scrie fiul sau ales pentru activare. Daca nodul respectiv nu are fii inactivi se va scrie cifra 0.
   
    Exemplu :
   
Fisierul INPUT.TXT :
   6
   2 1
   3 1
   4 2
   5 2
   6 3
   4
 Fisierul OUTPUT.TXT :
   6
   2 5 2 1 3 1
   4 0 5 2 6 3
 
  Timp limita de executie pe test : 1 secunda/test.
e executie pe test : 1 secunda/test.                         x    t    q    m    i    e    `    \   X                                               	            x    u   u .  u J  u   u   u   u    u o  u   u   u %  u *  u z  u   u   u  <<    x   x   x   x   x   x   x   x   x   x &  x ,  x D  x J  x Z  x j  x m  x   x   x  << 
       inactive. Initial toate nodurile sunt
 inactive. In acest arbore, deplasarea de la nodul i la nodul j este posibila
  Times New Roman  0Modern   toarele conditii :
   - nodul j este ascendent sau descendent direct al lui i(tata sau fiu);
