Laiko ribojimas: 1s

Atminties ribojimas: 64MB

Duomenų failas: tiltai.in

Rezultatų failas: tiltai.out

Jei norite pateikti savo sprendimą - prisijunkite.

Tiltai ir tuneliai

Kartais universiteto miestelyje būna labai šlapia. Kartais būna šalta. Nors neretai būna malonu būti lauke, pasitaiko dienų, kai gerokai maloniau būti viduje.

Laimei, miestelio planuotojai palengva jungia įvairius pastatus tiltais ir tuneliais. Deja, ne visada įmanoma patekti iš vieno pastato į kitą, neišėjus į lauką, nes dar trūksta tiltų ar tunelių.

Jūs norite surasti, kiek pastatų galima pasiekti nuo kiekvieno naujai pastatyto tilto ar tunelio.

Pradiniai duomenys

Pirmoje eilutėje yra vienas sveikasis skaičius N, pastatytų tiltų ir tunelių kiekis (1\\leN\\le100000). Laikykite, kad pradžioje visi pastatai yra pastatyti, bet dar nėra nė vieno tilto ar tunelio.

Tolesnėse N eilutėse yra aprašomi statomi tiltai ar tuneliai, jų statymo tvarka. Eilutėje yra dviejų pastatų, kuriuos jungia naujasis tiltas ar tunelis, pavadinimai. Pastato pavadinimą sudaro iki 20 didžiųjų ir mažųjų lotyniškų raidžių. Didžiosios ir mažosios raidės laikomos skirtingomis.

Rezultatai

Po kiekvieno tilto ar tunelio pastatymo, atskiroje eilutėje pateikite nuo to tilto ar tunelio pasiekiamų pastatų kiekį.

Pavyzdys

Duomenys Rezultatai
3
MC DC
DC Eng
MC MThree
2
3
4