Solução por Thiago Mota
Se imaginarmos as pessoas como vértices de um grafo e as listas de amigos como arestas podemos imaginar a mesa como sendo um grafo bipartido, de tal forma que um lado da mesa deve estar colorido de uma cor diferente do outro lado, logo a questão se resume em checar se o grafo é bipartido ou não, segue o código:
https://gist.github.com/Thiago4532/dce130bcd2674163ae4a60d94fb6686f