Условие
Задача F. ФЕРИБОТНИ ЛИНИИ
---
Архипелагът Островландия се състои от няколко острова. Всеки остров е свързан с поне една фериботна линия с някой от другите острови, като всички фериботни линии са двупосочни. Между някои два острова може да има и повече от една фериботна линия. Амбициозен владетел на Островландия решил да отвори още няколко фериботни лини така, че да може да се стигне от всеки остров до всеки друг остров – с един ферибот или с няколко ферибота, т.е. с прекачвания от един ферибот на друг в общо за двете линии пристанище. Напишете програма, която да намери минималният брой нови линии, които трябва да бъдат открити.
Вход: Програмата трябва да може да обработи по няколко тестови примера. Всеки тестов пример започва с ред на стандартния вход, на който е зададен броят N на фериботните лини. Следват N реда, на всеки от които са зададени, разделени с интервал, двата острова, които съответната линия свързва. Островите са означени с трибуквени низове от малки латински букви, в които буквата z не се използва. Различните острови са означени с различни низове. Краят на тестовите примери е означен с 0.
Изход: За всеки тестов пример, на ред на стандартния вход, програмата трябва да изведе броя на новите фериботни линии, които трябва да се открият, за да се изпълни желанието на владетеля.
Ограничения: 1 < N < 100000.
Примерен вход:
2
gen fen
jar far
0
Примерен изход:
1
« Предходна страница
Решение
Въпрос