Задача та же, что и 1156. Только формат инпута/аутпута изменили.

Разбиваем "граф враждебности" на компоненты связности, каждую компоненту — на две доли. Получаем задачу на рюкзак — необходимо в каждой из компонент взять одну из долей так, чтобы общий размер получился как можно ближе к N/2.