Балканская олимпиада по математике 2013 года | Казахстанские олимпиады

Некоторые участники математической олимпиады между собой дружат (дружба считается взаимной: если $A$ является другом $B$, то $B$ также друг $A$). Будем считать, что различные участники $A_1, A_2, \ldots, A_n$, где $n \geq 3$, образуют слабо-дружественный цикл, если $A_i$ не дружит с $A_{i+1}$, для всех $1 \leq i \leq n$ (здесь $A_{n+1} = A_1$), и не существует других недружащих пар цикла. При этом выполнены следующие свойства:
Для любого участника $C$ и любого слабо-дружественного цикла $S$, не содержащего $C$, множество $D$ участников из $S$, которые не являются друзьями $C$, состоит как максимум из одного элемента.
Докажите, что всех участников этой олимпиады можно рассадить по трём комнатам таким образом, чтобы любые два участника из одной и той же комнаты были друзьями.