End-Of-The-Line Augmented Problem of PPAD

Famous PPAD class of problems is formally defined by specifying one of its complete problems, known as End-Of-The-Line:

End-Of-The-Line Problem:
$G$ is a (possibly exponentially large) directed graph with no isolated vertices, and with every vertex having at most one predecessor and one successor. $G$ is specified by giving a polynomial-time computable function $f(v)$ (polynomial in the size of $v$) that returns the predecessor and successor (if they exist) of the vertex $v$. Given a vertex $s$ in $G$ with no predecessor, find a vertex $t≠s$ with no predecessor or no successor. (The input to the problem is the source vertex s and the function $f(v)$). In other words, we want any source or sink of the directed graph other than $s$.

Let's consider the slightly augmented version of End-Of-The-Line problem.

End-Of-The-Line Augmented Problem: The definition is same as for End-Of-The-Line expect that it's required to find not a vertex $t≠s$ with no predecessor or no successor, but the exact end of the path of the given source vertex $s$.

Intuitively, it seems like End-Of-The-Line Augmented Problem is not more in PPAD, just because it requires something more stronger than End-Of-The-Line Problem. How to show that End-Of-The-Line Augmented Problem is NP-hard?

This question is answered in the original paper by Papadimitriou 1994 original paper (pdf). It turns out that the problem is not only NP-hard but also PSPACE-hard, this is theorem 2 on page 506.

StackExchange Computer Science Q#11604, answer score: 5