Запутался с множествами, нужна помощь

Есть следующая задача:

Вводится несколько строк по два слова в каждой - имена двух друзей. Дружба - вещь взаимная(с двух сторон!!!). Иначе люди - не друзья.

Необходимо вывести ответ в соответствии с примерами ниже - список друзей. Список состоит из имен людей, список выстроен в лексографическом порядке(по алфавиту) по возрастанию, после имени человека идет фраза " дружит с : ", далее следует список имен его друзей, выстроенный так же по возрастанию.

Пример_1
Ввод:
Mike Nike
Oleg Petr
Mike Petr
Ivan Oleg
Вывод:
Ivan дружит с : Oleg 
Mike дружит с : Nike Petr 
Nike дружит с : Mike 
Oleg дружит с : Ivan Petr 
Petr дружит с : Mike Oleg 
Пример_2:
Ввод:
Петр Иван
Иван Петр
Олег Иван
Петр Олег
Вывод:
Иван дружит с : Олег Петр 
Олег дружит с : Иван Петр 
Петр дружит с : Иван Олег 

Код у меня такой вот:

public class TestClass {
    private static Map<String, List<String>> friends = new TreeMap<>();
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String[] pairs;
        List<String> list = new ArrayList();
        while (in.hasNext()) {
            String s = in.nextLine();
            list.add(s);
        }
        for (String pair : list) {
            addFriends(pair);
        }
        printAllFriends();
    }
    public static void addFriends(String pair) {
        String first = pair.split(" ")[0];
        String second = pair.split(" ")[1];
        put(first, second);
        put(second, first);
    }
    private static void put(String one, String two) {
        if (!friends.containsKey(one)) {
            friends.put(one, new ArrayList<>());
        }
        friends.get(one).add(two);
    }
    public static void printAllFriends() {
        for (Map.Entry<String, List<String>> pair : friends.entrySet()) {
            pair.getValue().sort(Comparator.naturalOrder());
            System.out.println( pair.getKey() + " дружит с : " + String.join(" ",pair.getValue()));;
        }
    }
}

Все нормально с первым тестом - проходит, но на втором валится...такое чувство что не в алфавитном порядке сортирует и выводит, хотя вроде бы правильно все написал. Дайте добрый совет, что поправить чтоб работало?