During BFS I marked (so to not visit them again) only vertexes which were in the path instead of all visited vertexes. The program passed all the tests before 17 although its running time was exponential.

11 1
1 11
2 11
3 11
4 11
5 11
6 11
7 11
8 11
9 11
10 11
11 11

Ans: No