First consider a graph \(\bold{A}\) consisting of the edges in \(G\) that aren’t in \(S\). This graph may be split into several connected components (if it doesn’t split, we consider it a graph with one component). We can find these components using DSU or flood-fill.

Note that if two points on \(\bold{A}\) are connected, we can freely travel between them. Let’s build a new graph \(\bold{B}\) using the edges in \(S\), but with each component from \(\bold{A}\) compressed to a single vertex; this graph may have self-loops and/or multiple edges.

Now we have an undirected graph where we need to find a path that uses all edges exactly once. This is called an Eulerian path, and exists if and only if all edges are connected (which is always true for \(\bold{B}\)) and there are at most \(2\) vertices with odd degree.

Proof of necessity is pretty simple; except for the starting and the ending vertex, all vertices must have an equal number of “entries” and “exits”, and this is only accomplished if they are of even degree. If there are no vertices of odd degree the path forms a cycle, otherwise if there are two odd-degree vertices they are the start and end vertices. Having exactly one odd-degree vertex isn’t possible.

To prove sufficiency, you can construct it using Hierholzer’s algorithm. This problem doesn’t require you to implement it however, as you only need to answer Yes or No.