We need a lemma that replaces the $p$ in the Erdős-Ginzburg-Ziv theorem by $p-1$. This line of proof is modified from the proof on Zoltán Lóránt Nagy's PhD thesis, p.10.
Lemma. Let $(a_1,a_2,... ,a_{2p−2})$ be a sequence of $2p−2$ elements of $\mathbb Z_p$, where $p$ is a prime. Then there exists a subsequence $A$ of length $p-1$, in which the sum of the elements equals zero.
Proof. Let $b_n$ ($n=1 ... 2p-2$) indicate whether the element $a_n$ is in the subsequence, i.e. $b_n=1$ if $a_n \in A$ and $b_n=0$ otherwise.
Define the polynomial $f=\underset {n}\sum b_n+1$ and $g=\underset {n}\sum a_nb_n$.
The polynomial $P=(1-f^{p-1})(1-g^{p-1})- \gamma \underset{n} \prod (1-b_n)$ takes the value $0$ unlesss* $f=0$ and $g=0$, which means there are $p-1$ $b_n$s that are $1$ and the elements they indicate sum to $0$. By choosing $\gamma$ appropriately, we can let the degree of $P$ be $2p − 2$ and the monomial $\underset{n} \prod b_n$ having its coefficient nonzero. By the Combinatorial Nullstellensatz, the polynomial $P$ is nonzero for some choice of $b_n$s, i.e. there is a subsequence $A$ of length $p-1$, in which the sum of the elements equals zero.
*"A unlesss B" means "A iff (the negation of B)". The wording in the PhD thesis, "if and only if", is wrong.
Now we prove the main theorem.
Let $X$ be a sequence where the number of occurences of $x$ is one less than the number of occurences of $x$ in $S$ as the first index, i.e. $|\{i:X_i=x\}|=|\{y: (x,y)\in S\}|-1$. The sequence has length $2p-3$ if every element appears in $S$ as the first index, and at least $2p-2$ otherwise.
If $X$ has length $2p-3$, we may assume that the elements we choose have first indices $1,2,3...(p-1)$, and we try to find appropriate second indices. Let $Y_i$ be the set of second indices of the elements of $S$ having first index $i$ ($i \neq 0$). We may assume $\underset{i} \sum |Y_i|=2p-1$, for otherwise we can choose all the elements $(0,x)$ ($x \neq 0$). Thus $\underset{i} \sum |Y_i|-1=p$. By the Cauchy-Davenport theorem, $|\sum Y_i|-1 \geq \underset{i} \sum |Y_i|-1$ if $\sum Y_i$ is not the whole $\mathbb Z_p$, but this is impossible because $\underset{i} \sum |Y_i|-1=p$. ($\sum Y_i$ is the additive-combinatorial sumset of all the $Y_i$s.) So $0\in ∑Y_i$ and there is an appropriate choice of second indices.
If $X$ has length at least $2p-2$, we may find a $(p-1)$-subsequence $A$ in $X$ that sum to zero. This is our choice of first indices, and the point is also trying to find appropriate second indices. Let $Y_i$ be the set of k-sums of second indices of the elements of $S$ having first index $i$ ($i \in A$), where $k$ is the number of occurences of $i$ in $A$. As $k$ is smaller than the number of elements in $S$ having first index $i$ (by the definition of $X$), the set $Y_i$ has size at least (number of occurences of $i$ in $A$)+1. Now $|\sum Y_i|-1 \geq \underset{i} \sum |Y_i|-1$ if $\sum Y_i$ is not the whole $\mathbb{Z} _p$, but this is impossible because $\sum |Y_i|-1 \geq |A| = p-1$. So $0\in ∑Y_i$ and there is an appropriate choice of second indices.