I implemented a simple BFS for this problem, which should give the shortest path in this case, but got only 3 test cases correct.

My solution: http://pastebin.com/thVPJZbK

When I looked at the test data from this page: All INOI contest problems, the test outputs seemed to be having a non-optimal path (probably using DFS) from the source to the destination.

The problem description states that if multiple routes are possible, print any one of them. But it seems the server doesn't find my solution to be correct.

Please help.