Distance preserving local isomorphims implies elementary equivalence I received some homework on model theory and I got stuck.

Let $A$ be a set and $f:A\to A$ a function. For all $a,b\in A$ we define dist$_f(a,b) = n$ if $f^n(a)=b$ or $f^n(b) = a$ and there is no $i < n$ such that $f^i(a)=b$ or $f^i(b) = a$, and dist$_f(a,b) = \infty$ if there is no such $n$.

The question revolves around the structures $(\mathbb{Z}, S)$ and $(\mathbb{Z}, S\circ S)$ where $S$ is the successor function which we view as a relation rather as a function.

Prove: for each $m,n$ for each local isomorphism $f = \{(z_0, w_0),\dots,(z_{n-1},w_{n-1})\}$ from $(\mathbb{Z}, S)$ to $(\mathbb{Z}, S\circ S)$, if $f$ preserves distances up to $2^m$, that is if dist$_S(z_i, z_j) < 2^m$ or dist$_{S\circ S}(w_i,w_j) < 2^m$ then dist$_S(z_i, z_j) =$ dist$_{S\circ S}(w_i,w_j)$, then $(\mathbb{Z}, S, z_0, \dots, z_{n-1})\equiv_m(\mathbb{Z},S\circ S, w_0, \dots, w_{n-1})$.

I know it is sufficient to show that $f \in LI_m((\mathbb{Z}, S),(\mathbb{Z}, S\circ S))$.
However, actually showing this gives me headaches. I tried a similar approach that is used when proving that $f$ preserves distances up to $2^p$ if and only if $f\in LI_p(\mathfrak{A},\mathfrak{B})$ with $\mathfrak{A}$ and $\mathfrak{B}$ both discrete linear orders without endpoints but that did not work out.
I generally have difficulties with these local isomorphisms so general tips/ideas/insights about them are also welcome. I thank you in advance.
Edit: I was asked to recall the definition of $LI_m(\mathfrak{A}, \mathfrak{B})$.
Let $\mathfrak{A} = (A, R_0,\dots, R_{l-1}, c_0,\dots,c_{p-1})$ and $\mathfrak{B} = (B, T_0,\dots, T_{l-1}, d_0,\dots,d_{p-1})$ be two relational structures.
$LI_m(\mathfrak{A},\mathfrak{B})$ is inductively defined as:

*

*$LI_0(\mathfrak{A},\mathfrak{B}) = LI(\mathfrak{A},\mathfrak{B})$

*$f\in LI_{m+1}(\mathfrak{A}, \mathfrak{B})$ if for every $a\in A$ there exists a $b\in B$ such that $f\cup \{(a,b)\}\in LI_m(\mathfrak{A},\mathfrak{B})$ and for every $b\in B$ there exists a $a\in A$ such that $f\cup \{(a,b)\}\in LI_m(\mathfrak{A},\mathfrak{B})$
 A: First: it helps have a picture in your head of $(\mathbb{Z},S\circ S)$: it's just the disjoint union of two isomorphic copies of $(\mathbb{Z},S)$: the first copy consists of the even numbers, and the second copy consists of the odd numbers, each with the function $n\mapsto n+2$.
Second: The statement is not true unless by "preserving distance" you mean "preserving distance and direction". That is, if $\mathrm{dist}_S(a,b) = d$ and $S^d(a) = b$, then $(S\circ S)^d(f(a)) = f(b)$ (and hence $\mathrm{dist}_{S\circ S}(f(a),f(b)) = d$). Indeed, consider the local isomorphism $0\mapsto 4$ and $2\mapsto 0$. This preserves distances up to $2^1 = 2$, since $\mathrm{dist}_S(0,2) = 2$ and $\mathrm{dist}_{S\circ S}(4,0) = 2$, but it is not in $LI_1$, since we cannot extend to a local isomorphism including $1$ in the domain: we have $S(0) = 1$ and $S(1) = 2$, but there is no $z$ such that $(S\circ S)(4) = z$ and $(S\circ S)(z) = 0$.
Ok, but once you adopt the stronger meaning of "preserving distance", then you can prove by induction on $m$ that if $f$ preserves distances up to $2^m$, then $$f\in LI_m((\mathbb{Z},S,z_0,\dots,z_{n-1}),(\mathbb{Z},S\circ S,w_0,\dots,w_{n-1})).$$
The base case $m = 0$ is trivial, since we have assumed $f$ is a local isomorphism, so it is in $LI = LI_0$.
Now suppose $f$ preserves distances up to $2^{m+1}$. I claim that for all $z_n\in \mathbb{Z}$, there is $w_n\in \mathbb{Z}$ such that $f' = f\cup \{(z_n,w_n)\}$ preserves distances up to $2^m$.
Case 1: For all $i<n$, $\mathrm{dist}_S(z_i,z_n) > 2^m$. Then we can pick any $w_n\in \mathbb{Z}$ such that for all $i<n$, $\mathrm{dist}_S(w_i,w_n) > 2^m$. Since $f$ preserves distances up to $2^m$, so does $f'$.
Case 2: There is some $i<n$ such that $\mathrm{dist}_S(z_i,z_n) = d \leq 2^m$. If $S^d(z_i) = z_n$, let $w_n = (S\circ S)^d(w_i)$. If $S^d(z_n) = z_i$, let $w_n$ be such that $(S\circ S)^d(w_n) = w_i$. Since $f$ preserves distances up to $2^m$ between $z_i$ and $z_j$ with $i,j<n$, so does $f'$. We need to check that $f'$ preserves distances up to $2^m$ between $z_n$ and $z_j$ with $j<n$.
If $\mathrm{dist}_S(z_j,z_n) = d' \leq 2^m$, then $\mathrm{dist}_S(z_i,z_j)\leq d+d' \leq 2^{m+1}$. Say $S^{d''}(z_j) = z_i$, with $d'' \leq 2^{m+1}$. Since $f$ preserves distances (and directions!) up to $2^{m+1}$, $(S\circ S)^{d''}(w_j) = w_i$. Then breaking into cases about where $z_n$ falls relative to $z_i$ and $z_j$ (i.e., the ordering of the triple $(z_i,z_j,z_n)$ in $\mathbb{Z}$), you can compute that $f'$ preserves the distance (and direction!) between $z_j$ and $z_n$.
It follows by induction that $f' \in LI_m((\mathbb{Z},S,z_0,\dots,z_{n}),(\mathbb{Z},S\circ S,w_0,\dots,w_{n}))$.
A similar argument in the other direction shows that for all $w_n\in \mathbb{Z}$, there is $z_n\in \mathbb{Z}$ such that $f' = f\cup \{(z_n,w_n)\}$ preserves distances up to $2^m$. By induction, $f' \in LI_m((\mathbb{Z},S,z_0,\dots,z_{n}),(\mathbb{Z},S\circ S,w_0,\dots,w_{n}))$.
So $f\in LI_{m+1}((\mathbb{Z},S,z_0,\dots,z_{n-1}),(\mathbb{Z},S\circ S,w_0,\dots,w_{n-1}))$.
