Fişierul intrare/ieşire:	pitici4.in, pitici4.out	Sursă	Algoritmiada 2010, Runda 1
Autor	Paul-Dan Baltescu	Adăugată de	Paul-Dan Baltescu •pauldb
Timp execuţie pe test	0.075 sec	Limită de memorie	20480 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Pitici4

Laura locuieşte împreună cu cei N pitici. Într-una din zilele trecute, piticii au facut o plimbare prin pădurea din jurul căsuţei lor. În timpul plimbării piticii au format mai multe grupuri, fiecare pitic formând un grup cu prietenii lui cei mai apropiaţi. Cum cărările pădurii sunt destul de înguste, două grupuri de pitici nu puteau merge în paralel. Din păcate, în astfel de situaţii când piticii se pun pe povestit se întâmplă să-şi uite bunele maniere şi curând au devenit atât de gălăgioşi încât au ajuns să le deranjeze pe restul vieţuitoarelor din pădure. Laura a aflat aceste lucruri si s-a hotărât să îi certe, dar mai întâi a dorit să afle cum erau aceştia aşezaţi în grupuri. Piticii nu doresc să-şi trădeze prietenii apropiaţi şi, de aceea, tot ce sunt de acord să-i spună Laurei sunt fraze de tipul următor: Numărul total de pitici din alte grupuri ce se aflau în faţa mea şi în spatele meu este A_i şi, respectiv, B_i. Unii pitici mai isteţi şi-au dat seama că aceste informaţii îi sunt suficiente Laurei pentru a reconstitui aşezarea lor pe grupuri şi, pentru a o încurca pe fată, au minţit. Cum socoteala nu a ieşit, Laura a înţeles că unii pitici au minţit-o. Cum nu mai poate reconstitui aşezarea piticilor, ea doreşte să ştie care este numărul maxim de pitici a căror informaţii nu se contrazic.

Cerinţă

Cunoscând informaţiile furnizate de pitici, determinaţi numărul maxim de pitici a căror informaţii nu se contrazic.

Date de intrare

Fişierul de intrare pitici4.in va conţine, pe prima linie, numărul întreg N. Pe următoarele N linii se găsesc câte două numere întregi A_i şi B_i corespunzătoare afirmaţiilor făcute de pitici.

Date de ieşire

În fişierul de ieşire pitici4.out va conţine un singur număr întreg reprezentând numărul maxim de pitici a căror informaţii nu se contrazic.

Restricţii

• 1 ≤ N ≤ 5 000

Exemplu

Explicaţie

Exemplul 1:

Putem presupune că există 3 grupuri: primul de 5 pitici, al doilea de 1 pitic şi ultimul de 3 pitici. Pentru această aşezare pe grupuri, piticii a căror informaţii nu se contrazic sunt 2, 4, 5, 6, 7 şi 8. Piticii 2, 6 şi 7 ar aparţine primului grup, piticul 5 formează al doilea grup, iar piticii 4 şi 8 ar aparţine celui de-al treilea grup. Această aşezare pe grupuri corespunde numărului maxim de pitici a căror informaţii nu se contrazic pe acest exemplu.

Cum se trimit solutii?