Q. Друзья друзей

Теория шести рукопожатий — социологическая теория, согласно которой любые два человека на Земле разделены не более, чем пятью уровнями общих знакомых (и, соответственно, шестью уровнями связей). Формальная математическая формулировка теории: диаметр графа знакомств не превышает 6. Мы не станем так сильно углубляться в дружественные связи и пока нам хватит только двух уровней. Напишите программу, которая по списку дружественных пар для каждого человека определяет список «друзей 2-го уровня».

Формат ввода

В каждой строке записывается два имени.
Окончанием ввода служит пустая строка.

Формат вывода:

Выведите список всех людей и их «друзей 2-го уровня» в формате «Человек: Друг1, Друг2, …».
Список людей и друзей в каждой строке требуется вывести в алфавитном порядке без повторений.

Пример

Ввод

Иванов Петров
Иванов Сергеев
Васильев Петров
Сергеев Яковлев
Петров Кириллов
Петров Яковлев

Вывод

Васильев: Иванов, Кириллов, Яковлев
Иванов: Васильев, Кириллов, Яковлев
Кириллов: Васильев, Иванов, Яковлев
Петров: Сергеев
Сергеев: Петров
Яковлев: Васильев, Иванов, Кириллов

Ввод

Николай Фёдор
Николай Женя
Фёдор Женя
Фёдор Илья
Илья Фёдор

Вывод

Женя: Илья
Илья: Женя, Николай
Николай: Илья
Фёдор:

Решение

Довольно запутанная задача, которая вызывает затруднения у многих учащихся. Ее запутанность возникает от того, что в голове достаточно сложно формализовать понятие “друзья друзей”.

Чаще всего рассуждения идут по достаточно простой схеме:
Собираем в словарь прямых друзей, при этом не забываем, что строка “Иванов Сидоров” означает что у нас должно появиться две пары друзей – Иванов-Сидоров и Сидоров-Иванов.
После чего собираем словарь “друзей друзей”. Для этого надо для каждого друга собрать всех его прямых друзей.
Казалось бы на этом задача выполнена и тест должен пройти, но возникает проблема.
В списке, присутствует сам “виновник торжества”, а он себе другом быть не может. Поэтому надо позаботиться, о том, чтобы его исключить.
Но и это еще не все, тест все равно не проходит. А все потому, что есть неочевидное следствие прошлой проблемы – прямые друзья, оказавшиеся в списке друзей друзей, тоже должны быть исключены.
После исключения прямых друзей остается отсортировать и вывести список.

friends = {}  # словарь прямых друзей

while pair := input():
    friend1, friend2 = pair.split()
    friends[friend1] = friends.get(friend1, set()) | set([friend2])
    friends[friend2] = friends.get(friend2, set()) | set([friend1])

friends_of_friends = {}  # словарь друзей друзей

for name in sorted(friends):
    for person in friends[name]:
        friends_of_friends[name] = friends_of_friends.get(
            name, set()) | friends[person]

for name in friends_of_friends:
    friends_of_friends[name].discard(name)  # удаляем самого себя
    friends_of_friends[name] -= friends[name]  # удаляем прямых друзей

    friends_of_friends[name] = sorted(friends_of_friends[name])

    print(f'{name}: {", ".join(friends_of_friends[name])}')