Hello everyone,

I have recently started to learn about graph theory and studied DFS and BFS. I was solving E — Shortest Path

The approach I thought

First put all the blocked roads into a set of triplets, then do a BFS with a condition. The condition was, before adding the adjacent nodes of the current node in the queue just check if its parent and parent's parent i.e. Let's say we have visited A -> B and now we have a child C then check if this triplet (A, B, C) is present in the set or not. If it does than do not visit the node C and continue with the other adjacent nodes of node B other than C.

The problem I am facing is, with the third test case. As this approach is not the right one, it is not reaching at the end for the last test case. i.e.

4 4 2
1 2
2 3
3 4
1 3
1 2 3
1 3 4

The valid path for this test case is 1 -> 3 -> 2 -> 3 -> 4 but I am getting -1.

Here is what I have implemented — Code

I have spent more than an hour but not getting any idea how can I visit the nodes as in the last case.

Am I required to learn any new algo? Any hints will be appreciated.

Thank you :)