Олимпиадные задачи из источника «10 класс, 1 тур» - сложность 3 с решениями

В городе "Многообразие" живут<i>n</i>жителей, любые два из которых либо дружат, либо враждуют между собой. Каждый день не более чем один житель может начать новую жизнь: перессориться со всеми своими друзьями и подружиться со всеми своими врагами. Доказать, что все жители могут подружиться. <i>Примечание.</i>Если<i>A</i>— друг<i>B</i>, а<i>B</i>— друг<i>C</i>, то<i>A</i>— также друг<i>C</i>. Предполагается также, что среди любых троих жителей хотя бы двое дружат между собой.