spoj
Състезание
Задача
F
Наименование
ФЕРИБОТНИ ЛИНИИ

Условие

Задача F. ФЕРИБОТНИ ЛИНИИ 
---
Архипелагът Островландия се състои от няколко острова. Всеки остров е свързан с поне една фериботна линия с някой от другите острови, като всички фериботни линии са двупосочни. Между някои два острова може да има и повече от една фериботна линия. Амбициозен владетел на Островландия решил да отвори още няколко фериботни лини така, че да може да се стигне от всеки остров до всеки друг остров – с един ферибот или с няколко ферибота, т.е. с прекачвания от един ферибот на друг в общо за двете линии пристанище. Напишете програма, която да намери минималният брой нови линии, които трябва да бъдат открити. 

Вход: Програмата трябва да може да обработи по няколко тестови примера. Всеки тестов пример започва с ред на стандартния вход, на който е зададен броят N на фериботните лини. Следват N реда, на всеки от които са зададени, разделени с интервал, двата острова, които съответната линия свързва. Островите са означени с трибуквени низове от малки латински букви, в които буквата z не се използва. Различните острови са означени с различни низове. Краят на тестовите примери е означен с 0. 

Изход: За всеки тестов пример, на ред на стандартния вход, програмата трябва да изведе броя на новите фериботни линии, които трябва да се открият, за да се изпълни желанието на владетеля. 

Ограничения: 1 < N < 100000. 

Примерен вход: 
2 
gen fen 
jar far 
0 

Примерен изход:
1 

« Предходна страница Решение Въпрос