The sanctums and portals form a directed, unweighted graph with ~N~ nodes and ~M~ edges. For each artifact ~i~, we'll need to compute the shortest distance ~D1_i~ from node ~1~ to node ~S_i~, as well as the shortest distance ~D2_i~ from node ~S_i~ to node ~1~. If ~D1_i~ or ~D2_i~ are infinite for any ~i~ (in other words, if no paths exist connecting those nodes), then we should output -1. Otherwise, the answer will be the sum of ~D1_{1 \dots K}~ and ~D2_{1 \dots K}~.

Computing all of the shortest distances ~D1_{1 \dots K}~ can be done in ~\mathcal O(N+M)~ time with a standard application of breadth-first search (BFS), starting from node ~1~.

However, computing the shortest distances ~D2_{1 \dots K}~ may be more problematic. We could initiate a separate breadth-first search starting from each node ~S_{1 \dots K}~, but that approach would be too slow to receive full marks, having a time complexity of ~\mathcal O(K(N+M))~. We can instead imagine an alternate version of the graph in which the directions of all edges are reversed (known as the transpose graph). Performing a single breadth-first search on the transpose graph starting from node ~1~ can allow us to compute all of the shortest distances ~D2_{1 \dots K}~ in just ~\mathcal O(N+M)~ time as well.