For the first subtask, note that ~M=N-1~. This means that the graph is a tree, meaning that there is only one path from ~A~ to ~B~. Thus we can just run a BFS or DFS from ~A~ to ~B~, with the answer being ~|V-d|~.

Time Complexity: ~\mathcal O(N)~

For the second subtask, it suffices to simply check every possible path in the graph from ~A~ to ~B~ and then get the smallest ~|V-d|~ of all those paths. One method of doing this is a DFS traversal of every path in the graph starting from ~A~.

Note that due to the number of edges (~M=N-1~) in the first subtask, this approach also works for it.

Time Complexity: ~\mathcal O(N!)~

For the final subtask, note that we can use a visited array to skip redundant paths. Two paths from ~A~ to a vertex ~v~ are redundant if they both have visited the same nodes. The implementation is left as an exercise to the reader.

We can prove this by looking at any two paths from ~A~ to any vertex ~v~ that has visited the same vertices. We can make two observations about these paths.

1. Both paths have the same length, since it's not allowed to backtrack and they visited the same [amount of] vertices.
2. The vertices that both paths can visit from ~v~ onward are the same, since they have already visited the same vertices and the paths cannot backtrack.

These observations show that both paths are functionally the same and thus it would be redundant to search onward from any more than one of the paths.

Time Complexity: ~\mathcal O(N \cdot 2^N)~

Author's note: Note that this problem is extremely similar to CCO '15 P2 - Artskjid, hence the [very original] problem name.