Динамика

Вот задача:http://codeforces.ru/contest/6/problem/D.
Не придумывается алгоритм решения.
В других некоторых сданных программах используется dfs, но непонятно как связать с графом.
Хотя, видимо, решается динамикой.
Наведите на путь решения!