Let \(P\) be one fixed shortest path from \(S\) to \(T\), and let the length of \(P\) be \(X\).

[1] When there exists a vertex on \(P\) (excluding \(S\) and \(T\)) that has degree at least \(3\)

Let \(V\) be such a vertex on \(P\) with degree \(\geq 3\). Take some vertex \(U\) connected to \(V\) that is not on \(P\). In this situation, you can achieve the goal in \(2X + 2\) moves as follows:

• Move piece A from \(S\) to \(U\).
• Move piece B from \(T\) to \(S\).
• Move piece A from \(U\) to \(T\).

From now on, check whether the goal can be achieved in \(2X + 1\) moves or fewer.

If both pieces A and B pass through all vertices on \(P\), then clearly it requires at least \(2X + 2\) moves.

If both pieces A and B skip at least one vertex on \(P\), one can make one of them to pass through all vertices on \(P\) to reduce the total number of moves.

If exactly one of the pieces (A or B) passes through all vertices on \(P\), one can assume that the other piece travel on another path \(Q\) from \(S\) to \(T\), where \(Q\) is the shortest of the paths other than \(P\). This is because one can choose a vertex on \(Q\) that is not on \(P\) and call it \(U\), enabling the same moves as above. This results in a total move count of \(X + |Q|\). Hence, you just need to check whether there is a path \(Q\) with \(|Q| \le X+1\). Under the condition \(|Q|\le X+1\), the shortest of the paths other than \(P\) is the same as the shortest of the walks other than \(P\), so one can use a BFS on \(2N\) vertices with an extra parameter “whether an edge not on \(P\) is used” to check whether such a path exists.

[2] When all the vertices on \(P\) (excluding \(S\) and \(T\)) have degree exactly \(2\)

Let \(Y\) be the minimum length of a path from \(S\) to \(T\) that does not use any edges in \(P\). Then, by the same reasoning as in [1], it is possible to achieve the goal in \(X+Y\) moves. Next, consider whether it can be done in fewer than \(X+Y\) moves.

Let \(S'\) be the closest vertex from \(S\) (reachable without going through \(T\)) that has degree not equal to \(2\). Let \(T'\) be the closest vertex from \(T\) (reachable without going through \(S\)) that has degree not equal to \(2\). The vertices \(S', S, T, T'\) line up in this order.

If both \(S'\) and \(T'\) have degree 1, the answer is -1. Otherwise, without loss of generality, assume:

• \(S'\) has degree at least \(3\).
• If \(T'\) also has degree at least \(3\), then the distance from \(S\) to \(S'\) is at most the distance from \(T\) to \(T'\).

Let \(Z\) be the distance from \(S\) to \(S'\). To complete the goal in fewer than \(X+Y\) moves, both pieces A and B must move along \(P\).

Since \(S'\) is on a simple path to \(T\), to get both pieces beyond \(S'\) on the way to \(T\), we need at least \(2X+4Z+4\) moves. However, if \(U_1\) and \(U_2\) are vertices connected to \(S'\) but not on the path from \(S'\) to \(T\), we can proceed as follows:

• Move piece A from \(S\) to \(U_1\) (needs \(Z+1\) moves).
• Move piece B from \(T\) to \(U_2\) (needs \(X+Z+1\) moves).
• Move piece A from \(U_1\) to \(T\) (needs \(X+Z+1\) moves).
• Move piece B from \(U_2\) to \(S\) (needs \(Z+1\) moves).

So \(2X+4Z+4\) moves is achievable. Doing the same at \(T\) would also require at least \(2X+4Z+4\) moves. Therefore, the smaller between \(2X+4Z+4\) and \(X+Y\) is the answer.

[3] Summary

Putting it all together:

• If there are multiple shortest paths from \(S\) to \(T\), the answer is \(2X\).
• Otherwise, if a path (or walk) of length \(X+1\) exists, the answer is \(2X+1\).
• Otherwise, if there is a vertex of degree \(\geq 3\) on the shortest path, the answer is \(2X+2\).
• Otherwise, the answer is the smaller of the following:
  • \(X+Y\), where \(Y\) is the shortest distance in the graph obtained by removing all edges on the original shortest path
  • \(2X+4Z+4\), where \(Z\) is the minimum distance from \(S\) or \(T\) to any vertex of degree \(\geq 3\)

Implementing the above approach correctly solves the problem in \(O(N+M)\) time.

Sample Implementation (Python3)