It is not true that DFS is not working here. I have solved this problem at first (before re-judging) with DFS. But After re-judging I got TLE and then I have attacked this problem with BFS and at that time I got WA. Finally I have managed to solve this `funny' problem with DFS with some pruning. I got the hint from Steven's page and that's why LATE THANKS to Steven.