IMO олимпиада по математике 2019 года | Казахстанские олимпиады

В социальной сети 2019 пользователей. Некоторые пользователи дружат с некоторыми другими, при этом отношение дружбы взаимно, то есть если пользователь $A$ дружит с пользователем $B$, то $B$ также дружит с $A$. Перестройки следующего типа производится последовательно, по одной перестройке за раз:
   выбираются три пользователя $A,$ $B$ и $C$ таких, что $A$ дружит и с $B$ и с $C$, но $B$ и $C$ не дружат между собой; после чего $B$ и $C$ становятся друзьями, но $A$ теперь не дружит ни с $B,$ ни с $C.$
   Изначально 1010 пользователей имеют по 1009 друзей, а 1009 пользователей имеют по 1010 друзей. Докажите, что существует последовательность перестроек, после которой каждый пользователь будет иметь не более одного друга.