"It is guaranteed that at least one solution exists", i.e. size of connecting component of friends  <= 6.

regroup all connecting component set by size and, how much people in this set like main, and side.
example: 1-group: 6 people
         2-group: 5 people : 2.1) 4 like main , 1 side or 2.2) 3 like main, 2 side
         3-group: 4 people : 3.1) 4 like main or 3.2) 3 like main 1 side 3.3) 2 like main, 2 side .
 ------------------------------------------------------------------
 ...........................................
-----------------------------------------------------------------


think permutations of this sets.