Space complexity of a variant of st-connectivity Consider a variant of STCON, called 2STCON, which is defined like this:
$$2STCON = \{\langle G,u,v \rangle \} \mid \text{$G$ is a graph with } \mathit{two} \text{ paths from $u$ to $v$} \} $$
This means the only difference to the &quot;normal&quot; STCON is that there are two paths instead of just one between $u$ and $v$.
I need to show that 2STCON belongs to NL.
What is the  best way to approach this problem?
The usual proof that STCON is in NL works as follows: you guess a path from $u$ to $v$, and verify it step by step.
A very similar proof works for 2STCON: you guess two paths from $u$ to $v$, and verify them step by step. As you verify them, you also verify that they are different: either the length is different, or the $i$-th vertex is different, for some $i$.