Всем доброго времени суток!

Уже очень долго пытаюсь решить эту задачу: http://acm.timus.ru/problem.aspx?space=1&num=2006 возникла идея сжать граф и пытаться удалять по одной вершине кратчайшего пути, но как именно нужно строить новый граф придумать не получается