Consiliul tribului

trib

==Include(page="template/taskheader" task_id="trib")==

== include(page="template/taskheader" task_id="trib") ==

Tribul Kazooba este format din $N$ oameni ce doresc sa se reuneasca pentru un consiliu al tribului. Oamenii sunt cu totii descendenti a unui singur om, care este seful tribului. Deoarece toti oamenii acestui trib au o viata lunga, ascendentii fiecarei persoane, chiar si seful tribului, sunt in viata si se vor prezenta la consiliu.
Oamenii ajung la consiliu intr-o anumita ordine si se aseaza la mese la venire. Ei stau intr-un rand de mese paralele. Prima masa este asezata la poalele Muntelui Sfant, si randul se extinde infinit spre vest (partea opusa muntelui). Pe de alta parte, fiecare om ar dori sa fie cat mai aproape de divinitate, asa ca, atunci cand soseste, el se aseaza catre masa cea mai apropiata de Muntele sfant la care nu s-a asezat nici unul dintre copiii sau tatal lui.
Ca de obicei, zeii tribului au o inclinatie aparte pentru frumusete. Ei ar dori sa ceara membrilor tribului sa soseasca la consiliu intr-o ordine in care numarul de mese ocupate sa fie maxim. Din pacate, ei nu au nici un fel de inclinatie pentru programare, asa ca v-au cerut voua sa scrieti un program pentru asta.

Poveste ...

h2. Cerinta

Scrieti un program care determina numarul maxim de mese ce poate fi ocupat la consiliu.

...

h2. Date de Intrare

h2. Restrictii

Prima linie a fisierului $trib.in$ contine un numar intreg $N$, reprezentand numarul de oameni din trib. Oamenii sunt numerotati de la 1 la $N$; seful lor este numarul 1. Fiecare dintre urmatoarele linii contin doua numere $A, B$ cu semnificatia "exista o legatura directa de rudenie intre persoanele $A$ si $B$". Relatiile descrise in fisierul de intrare sunt corecte (de exemplu nu exista cicluri, iar fiecare persoana este unul dintre descendentii sefului).

...

h2. Date de Iesire

h2. Date de intrare

Fisierul $trib.out$ are o singura linie ce contine numarul maxim de mese care pot fi ocupate.

...

h2. Restrictii si precizari

h2. Date de iesire

* $1 < N &le; 100 000$
* pentru $30%$ dintre teste $N &le; 1000$
* orice masa are capacitate nelimitata

...

h2. Exemplu

table(example). |_. trib.in |_. trib.out |
| 5
1 4
3 2
1 3
3 5 | 3 |
 
h3. Explicatie
 
Daca oamenii sosec in ordinea 2 4 1 5 3, ei se aseaza astfel:
-2 se aseaza la prima masa
-4 se aseaza la prima masa
-1 are un fiu (4) la prima masa asa ca se aseaza la masa a 2-a
-5 se aseaza la prima masa
-3 are 2 fii la prima masa (2 si 5) si pe tatal sau (1) la a 2-a masa, asa ca se aseaza la a 3-a masa
 
==Include(page="template/taskfooter" task_id="trib")==
 

| trib.in | trib.out |
| linia1
linia2
linia3
| linia1
linia2
|
== include(page="template/taskfooter" task_id="trib") ==

875