Sponsored
Sponsored
Use these hints if you're stuck. Try solving on your own first.
Can you solve the problem if the whole graph is connected?
Notice that if the graph is connected, you can always use any edge of the graph in your path.
How to solve the general problem in a similar way? Remove all the nodes that are not connected to 1 and n, then apply the previous solution in the new graph.