Šeštadieninė informatikos olimpiadininkų mokykla

Du geri draugai pasipasakoja visas paslaptis. Vienas asmuo gali turėti kelis gerus draugus, kurie tarpusavyje gali ir nebūti geri draugai. Pavyzdžiui, A gali draugauti su B ir su C, nors B ir C nėra geri draugai. Tokiu atveju B paslaptys pasieks C ir atvirkščiai – C paslaptys pasieks B per A. Tokios grandinės gali būti ilgos ir, kaip sakoma, paslaptys greit pasklinda po visą pasaulį.

Užduotis

Reikia parašyti programą, kuri nustatytų, kokį didžiausią paslapčių skaičių galima patikėti duotai asmenų grupei, kad kiekvienas asmuo žinotų tik po vieną paslaptį.

Pradiniai duomenys

Pradinius duomenis sudaro gerų draugų poros. Asmeny skoduojami skaičiais iš intervalo .

Pirmoje eilutėje nurodytas draugų porų skaičius. Kiekviena tolesnė eilutė skiriama vienai draugų porai. Joje du skaičiai – asmenų kodai.

Asmenų sąrašas atskirai nepateikiamas. Laikoma, kad kiekvienas jų paminėtas porų sąraše.

Rezultatai

Rezultatas – vienas sveikasis skaičius.

Pavyzdžiai

6
25 16
40 1
18 16
16 25
2 6
2 4

3