problem A ICPC Kanpur Site 2006

[skinnyguy]

you can see the problem description here...
http://acmicpc-live-archive.uva.es/nuev ... php?p=3764

no one solved the problem during the contest time and the problem was used again by the kanpur site for there online preliminary this year.
i can't seem to think of framing this in any form of graph theoretic algorithms.
i wanted to know if this problem needs some kind of backtracking or there exists some algorithm for solving it?

please help