У Кати в итоге должно быть сделано как минимум (1109, 1142, 1128, 1139 и еще одна из "New")
У Миши - всё! (если времени мало, пусть напишит хотя бы 1045-ю и 1142-ю)
Саша пусть сидит и делает хоть что-нибудь, ему полезно. В идеале должен сделать всё. Пусть начнет с 1142.

Всем не упомянутым нужно узнать про решение задачи 1128. И с нее же начать.

------

Решение 1128-й.
1) Всех в первую группу.
2) Если кому-то плохо, перекидываем его в другую группу.
3) У перекинутого было >= 2 врагов, стало <= 1. Значит число ребер уменьшилось => процесс конечен.

Про паросочетание:
1) Чтобы увеличить, нужно построить "дополняющую цепь"
2) Почему мы получим максимум? рассмотрим симметрическую разность текущего и максимального паросочетаний.
3) Она состоит из путей и циклов. Эти пути и циклы тоже "дополняющие".