timus 1609

Здравствуйте!

http://acm.timus.ru/problem.aspx?space=1&num=1609

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