Space complexity of a variant of st-connectivity
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$.