Идея максимального паросочетания кажется очевидной. Только надо проверить что оно полное и единственное. Первое проверяется легко. Про второе я забыл и обнаружил после получения WA на первом тесте (да, не проверил стандартный тест). Времени оставалась мало и надо было что-то придумать для проверки единственности. Первое что пришло это по очереди блокировать (т.е. запретить использование) каждый город, который входит в паросочетание и пробовать найти другое паросочетание. Сдав задачку в темную и получив после ОК я вроде и не думал о ней, пока не стал рассказывать идею решение своему другу. И как я вообще мог дойти до такой идеи, ведь правильно надо было блокировать ребро, а не город. Кому интересно вот решение.

Слабость тестов мне кажется очень очень плохо сказывается на подготовке, ведь все что придумывается на тренировках может в дальнейшем использоваться на серьезных соревнованиях. Поэтому хочется попросить всех авторов более серьезно относиться к подготовке задач. Спасибо за внимание.