The tests are weak!
I submitted simple BFS using adjacency matrix and got WA#8.
But my friend used adjacency list and got AC with the same algorithm.
So, the result depends on the order of edges in the input.
Admins, please, add some tests to fix this problem.

P.S. There is O(nm) correct solution.