\section{Proofs for Section~\ref{sec:goodness}}\label{app:goodness}

\subsection{Proof of Lemma~\ref{lem:cut}}\label{app:cut}

(1) A path from $x$ to $y$ avoiding $z$ would put $x$ and $y$ in one component of $H\setminus\{z\}$.
For the order, let $u,v$ both meet every path from $x$ to $Y$, and suppose that $u$ precedes $v$ on a
simple path $\gamma$ from $x$ to $y\in Y$ and $v$ precedes $u$ on a simple path $\gamma'$ from $x$ to
$y'\in Y$. Then $\gamma$ from $x$ to $u$ avoids $v$, and $\gamma'$ from $u$ to $y'$ avoids $v$, since
$v$ comes before $u$ on $\gamma'$. Their concatenation is a walk from $x$ to $Y$ avoiding $v$, which
contains a path from $x$ to $Y$ avoiding $v$, a contradiction. Equivalently, the cut vertices separating
$x$ from $y$ are the cut-vertex nodes strictly inside the path from $x$ to $y$ in the block--cut tree.

(2) Let $z$ separate $x$ from $y$. If $z=w$ it is the $+1$. Otherwise, if $z$ separated neither $x$ from
$w$ nor $w$ from $y$, paths $x\to w$ and $w\to y$ avoiding $z$ would give an $x$--$y$ walk avoiding $z$.
Since $z\notin\{x,y,w\}$, it is counted in $\piv_H(x,w)$ or in $\piv_H(w,y)$.

(3) Let $z\notin R$ separate $x$ from $y$ in $H$. Every $x$--$y$ path in $H''$ is an $x$--$y$ path in
$H$, so it contains $z$; since $H''$ is connected and contains $x$ and $y$, such a path exists, so
$z\in H''$, and $z$ separates $x$ from $y$ in $H''$. At most $|R|$ of the separating vertices lie in $R$.

(4) In the block--cut tree, the path from $z_t$ to $z_{t'}$ is a subpath of the path from $x$ to $y$,
and the cut-vertex nodes strictly inside it are $z_{t+1},\dots,z_{t'-1}$ for $t<t'$. These separate
$z_t$ from $z_{t'}$.

(5) Separating vertices are distinct and exclude $x$ and $y$.
\qed

\subsection{Proofs of Lemmas~\ref{lem:marked} and~\ref{lem:radius}}\label{app:marked}

\begin{proof}[Proof of Lemma~\ref{lem:marked}]
\emph{First moment.} Explore $C^D_x$ in a fixed, mark-independent order: query $\omega_x$; while some
discovered open vertex has an unqueried neighbour in $D$, query the first such neighbour in a fixed
order. Test the mark of each newly discovered open vertex immediately, and stop at the first mark or
when the cluster is exhausted ($x$ closed counts as exhausted). No vertex is queried twice. The
procedure terminates almost surely: if $C^D_x$ is infinite, its discovery sequence is infinite and the
independent marks give a mark almost surely. Let $T$ be the number of site queries and $N$ the number of
open vertices discovered when it stops. Conditionally on $\omega$, the discovery order of $C^D_x$ is
fixed, and $N$ is a geometric($h$) variable stopped at $|C^D_x|$; on $E$ it is that variable conditioned
to be at most $|C^D_x|$. In both cases its mean is at most $1/h$. Each discovered open vertex causes at
most $d$ further queries, so $T\le1+dN$, and $\E T\le(d+1)/h$ and $\E[T\mid E]\le(d+1)/h$.

Let $Z=\sum_{v\text{ queried}}(\omega_v-p_c)$ and $Q_v=\1\{v\text{ queried}\}$. The variable $Q_v$ is a
function of the marks and of the bits queried before $v$, so it is measurable without $\omega_v$. If $v$
is pivotal, set $\omega_v=1$: then $E$ holds, the procedure stops at a mark $m$, and the discovered set
is connected and contains $x$ and $m$, hence an $x$--$m$ path, which meets $v$; so $v$ is queried with
$\omega_v=1$, and since $Q_v$ does not depend on $\omega_v$, $Q_v=1$. If $v$ is not pivotal, $\1_E$ does
not depend on $\omega_v$. Conditioning on all other bits and the marks, $\E[(\omega_v-p_c)Q_v\1_E\mid
\text{rest}]$ is $0$ if $v$ is not pivotal, and $\E[(\omega_v-p_c)\omega_v\mid\text{rest}]=p_c(1-p_c)$
if $v$ is pivotal, since then $Q_v=1$ and $\1_E=\omega_v$. Hence
$\E[(\omega_v-p_c)Q_v\1_E]=p_c(1-p_c)\Pp(v\text{ pivotal})$; summation is allowed since
$\sum_v\E|\omega_v-p_c|Q_v\le\E T<\infty$. An open pivotal lies in $E$, and $\omega_v$ is independent of
the pivotality of $v$, so $p_c\Pp(v\text{ pivotal})=\Pp(v\text{ open pivotal})$. With
$N^+_{\mathrm{piv}}=N_{\mathrm{piv}}+\1_E$ the count including the root,
\begin{equation}\label{eq:score}
\E[Z\1_E]=(1-p_c)\E[N^+_{\mathrm{piv}}\1_E]\ge(1-p_c)\E[N_{\mathrm{piv}}\1_E].
\end{equation}
Each queried bit is a fresh Bernoulli($p_c$) variable given the transcript; the marks are independent
coins and enter neither $Z$ nor $T$. Hoeffding's lemma at the bounded stopping times $T\wedge n$ and
Fatou's lemma give $\E\exp(\lambda Z-\lambda^2T/8)\le1$. Now $\Pp(E)\ge p_ch$, since $x$ open and marked
suffices. With $c_{\mathrm m}=1+\log(1/p_c)/\log2$ and $h\le1/2$, $\log(1/(p_ch))\le c_{\mathrm m}\log(1/h)$. Conditional
Jensen gives
\[
\lambda\E[Z\mid E]\le\log(1/\Pp(E))+(\lambda^2/8)\E[T\mid E]\le c_{\mathrm m}\log(1/h)+\lambda^2(d+1)/(8h).
\]
With $\lambda=\sqrt{8c_{\mathrm m}h\log(1/h)/(d+1)}$ and~\eqref{eq:score},
$\E[N_{\mathrm{piv}}\mid E]\le(1-p_c)^{-1}\sqrt{c_{\mathrm m}(d+1)/2}\,\sqrt{\log(1/h)/h}$. Put
$C=\max\{1,(1-p_c)^{-1}\sqrt{c_{\mathrm m}(d+1)/2}\}$. Since $\sqrt{\log(1/h)/h}\ge\sqrt{2\log2}>1$ for $h\le1/2$,
$A_h\ge1$, and the case $i=1$ holds uniformly over $(D,x)$. The case $i=0$ is trivial.

\emph{Higher binomial moments.} Put $b_i(D,x)=\E[\binom{N_{\mathrm{piv}}}{i}\1_E]$ and $b_0(D,x)=\Pp(E)$.
We claim that, for $i\ge1$,
\begin{equation}\label{eq:recursion}
b_i(D,x)=\sum_{v\in D\setminus\{x\}}\ \sum_{\substack{W\subset D\text{ finite}\\x\in W,\ v\in\partial_DW}}
\Pp\bigl(C^{D\setminus\{v\}}_x=W\bigr)(1-h)^{|W|}\,b_{i-1}(D'_{W,v},v),
\end{equation}
with $D'_{W,v}=(D\setminus\Nb_D[W])\cup\{v\}$,
where $\partial_D$ and $\Nb_D$ are taken in $D$. There is no separate factor $p_c$: the openness of $v$
is part of the event $E'$ below, hence of $b_{i-1}(D',v)$. Decompose a selected $i$-set of open
non-root pivotals by its first element $v$ in the linear order.
\begin{itemize}
\item Given $v$, put $W=C^{D\setminus\{v\}}_x$, the root cluster with $v$ forced closed. On $E$ with $v$
an open non-root pivotal, $W$ contains $x$, has no marks, and is almost surely finite, since an infinite
$W$ carries a mark almost surely; and $v\in\partial_DW$, since $C^D_x$ is connected and $W$ is the
component of $x$ in $C^D_x\setminus\{v\}\ne C^D_x$. The event $\{C^{D\setminus\{v\}}_x=W\}$ is determined
by the bits of $W$ (open) and of $\partial_DW\setminus\{v\}$ (closed), and involves neither $\omega_v$ nor
any bit of $D'\setminus\{v\}$.
\item Given that event, if $v$ is open then $C^D_x=W\cup C^{D'}_v$. Indeed $C^D_x\setminus W$ consists of
$v$ and the other components of $C^D_x\setminus\{v\}$, each adjacent to $v$; it is connected, contains
$v$, and avoids $W$ and the closed set $\partial_DW\setminus\{v\}$, so it lies in $D'$ and in $C^{D'}_v$;
conversely $C^{D'}_v\subseteq C^D_x$. No vertex of $C^{D'}_v\setminus\{v\}$ is adjacent to $W$, since it
would lie in the closed set $\partial_DW\setminus\{v\}$. So $W$ is attached to $C^{D'}_v$ only through
$v$.
\item $W$ carries no mark, which gives the factor $(1-h)^{|W|}$, so $E$ holds if and only if
$E':=\{C^{D'}_v\text{ contains a mark}\}$ holds, and $E'$ requires $v$ open. Conversely, if $C^{D\setminus\{v\}}_x=W$, $W$ is unmarked and $E'$ holds, then $v$ is an open
pivotal for $E$: closing it gives $C^D_x=W$.
\item Every path from $x$ to a mark enters $C^{D'}_v$ only through $v$, and a vertex $u\in
C^{D'}_v\setminus\{v\}$ meets every $x$--mark path if and only if it meets every $v$--mark path inside
$C^{D'}_v$. So the open non-root pivotals of $E$ after $v$ are exactly the open non-root pivotals of $E'$
in the domain $D'$ with root $v$, and the earlier ones lie in $W$.
\item The bits and marks of $W\cup(\partial_DW\setminus\{v\})$ and of $D'$ are independent, and the law
of $(\omega,\text{marks})$ on $D'$ is the domain-$D'$ law. So the conditional contribution is
$b_{i-1}(D',v)$.
\item If the open non-root pivotals are $v_1<\dots<v_n$, the subsets with first element $v_j$ number
$\binom{n-j}{i-1}$, and $\sum_{j=1}^n\binom{n-j}{i-1}=\binom ni$. All terms are nonnegative, so
Tonelli's theorem justifies the decomposition without a priori moment bounds.
\end{itemize}
The case $i=1$ of~\eqref{eq:recursion} expresses $b_1$ through $b_0$. If $b_{i-1}\le A_h^{i-1}b_0$ for
every domain and root, then~\eqref{eq:recursion} gives $b_i(D,x)\le A_h^{i-1}b_1(D,x)\le A_h^ib_0(D,x)$,
uniformly over all $(D,x)$. Then $\E[(1+(2A_h)^{-1})^{N_{\mathrm{piv}}}\1_E]=\sum_i(2A_h)^{-i}b_i\le
2\Pp(E)$, and $\log(1+(2A_h)^{-1})\ge(4A_h)^{-1}$ for $A_h\ge1$, so Markov's inequality gives the tail
bound.
\end{proof}

Compared with~\cite[Lemma~3.3]{OAINU}, the changes are vertex queries ($T\le1+dN$, so $d$ becomes
$d+1$), $\Pp(E)\ge p_ch$ in place of $h$ (the constant $c_{\mathrm m}$), the root excluded from
$N_{\mathrm{piv}}$, and the recursion~\eqref{eq:recursion} with exterior $(D\setminus\Nb[W])\cup\{v\}$
and no factor $p_c$.

\begin{proof}[Proof of Lemma~\ref{lem:radius}]
On the event, choose a witness $y\in C_x$ with $\piv_{C_x}(x,y)\ge R:=\kappa M^\tau/2$ by a fixed ordering.
Mark vertices independently with probability $h$. The conditional probability that $y$ is the only mark
in $C_x$ is $h(1-h)^{|C_x|-1}\ge h(1-h)^M$. In that case every cut vertex $z\in C_x\setminus\{x,y\}$
separating $x$ from $y$ is an open non-root pivotal for $E=E(V,x,h)$, since closing $z$ separates $y$,
the only mark, from $x$. So $N_{\mathrm{piv}}\ge R$, and by Lemma~\ref{lem:marked},
\[
\Pp(s_x\le M,\ \rpiv\ge R)\le\frac2{h(1-h)^M}\exp\Bigl(-\frac R{4A_h}\Bigr).
\]
Set $X=\kappa^2M^{2\eps}/\log M$ and $h=X/(bM)=\kappa^2M^{-1+2\eps}/(b\log M)$, with $b$ a large constant
fixed below. Then $\kappa\le M^{1-\tau}$ gives $h\le1/(b\log M)\le1/2$; $\kappa\ge\kappa_0$ gives
$h\ge\kappa_0^2M^{-1+2\eps}/(b\log M)$, so $\log(1/h)\le2\log M$ for $M\ge M_0(\kappa_0,b,\eps)$; hence
$A_h=C\sqrt{\log(1/h)/h}\le C\sqrt{2b}\,M^{1/2-\eps}\log M/\kappa$ and $R/(4A_h)\ge X/(8C\sqrt{2b})$; and
$-\log(1-h)\le2h$ gives $M(-\log(1-h))\le2X/b$. The logarithm of the bound is therefore at most
$O(\log M)+2X/b-X/(8C\sqrt{2b})$. Choose $b$ so that the last two terms sum to at most $-c_1X$. Since
$X\ge\kappa_0^2M^{2\eps}/\log M$ dominates $\log M$, the bound holds for large $M$ with $c=c_1/2$.
\end{proof}

\subsection{Proof of Proposition~\ref{prop:good}}\label{app:good-proof}

We use the event $\mathrm{Bad}$, the witness $(A,B)$ with count $K$ and $\mathsf D=\dpiv(B)$, the two cases
and the set $J$ of Section~\ref{sec:good-proof}, and $\omega'$, the configuration $\omega$ with $J$
closed. Let $\mathrm{Bad}_K$ be the part of $\mathrm{Bad}$ whose chosen witness has count $K$, and let
$k\le K$ be the number of contacts of $B$.

We prove the claims of Case~2.
\begin{enumerate}[label=\textup{(\alph*)},leftmargin=2.2em]
\item \emph{$\gamma$ from $x$ to $a$ is open in $\omega'$.} Its vertices before $a$ are neither in $B$
($\gamma$ has not yet entered $B$, since the contact preceding the first $B$-vertex of $\gamma$ is at or
after $a$) nor contacts ($a$ is the first). Also $R\subseteq B$ and $a\notin J$.
\item \emph{In $\omega'$, the only open vertex outside $B''$ with a neighbour in $B''$ is $a$, and the
only neighbour of $a$ in $B''$ is $b^*$.} Let $y\notin B''$ be adjacent to $B''$. If $y\in B$, then
$y\in R$, since a vertex of $B\setminus R$ adjacent to the component $B''$ of $B\setminus R$ lies in
$B''$; so $y$ is closed in $\omega'$. If $y\notin B$, then $y\in\partial B$; vertices of $\partial B\cap
C_x$ are contacts, closed in $\omega'$ except $a$, and vertices of $\partial B\setminus C_x$ are closed
in $\omega$ and unchanged. Finally $N(a)\cap B''\subseteq N\setminus R=\{b^*\}$.
\item \emph{$\rpiv(C'_x,x)\ge\mathsf D/(2d)-d+1/2$.} By (a), $C'_x\supseteq\gamma[x,a]\cup\{b^*\}\cup B''$,
since $a\sim b^*$ and $B''$ is open and connected in $\omega'$. Let $\pi$ be a simple path in $C'_x$ from
$x$ to $v$. As $x\notin B''$, by (b) the path enters $B''$ only along the edge $a\to b^*$ and cannot
leave $B''$ except from $b^*$; so it visits $b^*$ once, and its part after $b^*$ is a $b^*$--$v$ path
inside $B''$. Hence every cut vertex of $B''$ separating $b^*$ from $v$, and $b^*$ itself, separate $x$
from $v$ in $C'_x$; none equals $x$ or $v$. Here $v\ne b^*$, because $M^\tau\ge4d^2$ and $\mathsf D>M^\tau$
give $\mathsf D/(2d)-d-1/2>d-1/2>0$. By Lemma~\ref{lem:pruning},
$\rpiv(C'_x,x)\ge\piv_{B''}(b^*,v)+1\ge\mathsf D/(2d)-d+1/2$.
\end{enumerate}

\paragraph{Both cases land in a radius-tail event.} Closing only shrinks clusters, so $s'_x\le s_x\le
M$. Since $\mathsf D>KM^\tau\ge M^\tau\ge4d^2$:
in Case~1, $(\mathsf D-1)/2\ge KM^\tau/2-1/2\ge KM^\tau/(4d)$; in Case~2,
$\mathsf D/(2d)-d+1/2\ge KM^\tau/(2d)-d\ge KM^\tau/(4d)$, because $KM^\tau/(4d)\ge d$. So $\omega'$ lies in
\[
O_K:=\{s_x\le M,\ \rpiv(C_x,x)\ge\kappa M^\tau/2\},\qquad\kappa=K/(2d),\quad1/(2d)\le\kappa\le M^{1-\tau}.
\]

\paragraph{Cost of the change.} No independence of the input-dependent choices is needed. We have
$|J|=m\le k\le K$ in Case~1 and $m\le(k-1)+(d-1)\le K+d$ in Case~2. Every vertex of $J$ is open in
$\omega$ and lies in $C_x$ (contacts lie in $C_x$, and $R\subseteq B\subseteq C_x$), and $\omega$ is
$\omega'$ with $J$ opened.
\begin{itemize}
\item \emph{Reconstruction count.} Put $Q_0=C_x(\omega')\ni x$; here $x\notin J$, since $x\in B$ in Case~1
and a contact equal to $x$ is $a$ in Case~2. List $J$ as $j_1,\dots,j_m$, where $j_i$ is the first
vertex, in a fixed order, of $J\setminus\{j_1,\dots,j_{i-1}\}$ adjacent to
$Q_{i-1}:=C_x(\omega'\text{ with }j_1,\dots,j_{i-1}\text{ opened})$. It exists: $Q_{i-1}\subseteq
C_x(\omega)$, and if $J\not\subseteq Q_{i-1}$ then $Q_{i-1}\ne C_x(\omega)$, so an edge of $C_x(\omega)$
leaves $Q_{i-1}$ to a vertex that is open in $\omega$ but not in $Q_{i-1}$, hence lies in $J$ and has not
been listed. Since $|Q_{i-1}|\le M$, each $j_i$ is one of at most $dM$ vertices of $\partial Q_{i-1}$,
which $\omega'$ and $j_1,\dots,j_{i-1}$ determine. So an output $\omega'$ has at most
$\sum_{m=0}^{K+d}(dM)^m\le(K+d+1)(dM)^{K+d}$ preimages in $\mathrm{Bad}_K$.
\item \emph{Probability ratio.} $\Pp(\omega)/\Pp(\omega')=(p_c/(1-p_c))^m\le\vartheta^{K+d}$ with
$\vartheta=\max\{1,p_c/(1-p_c)\}$.
\item \emph{Finite product.} On $\mathrm{Bad}_K$ every vertex of $C_x$ lies within distance $M-1$ of
$x$, and $J\subseteq C_x$. The events $\mathrm{Bad}_K$ and $O_K$ are determined by the bits in $B(x,M)$
(locality below), and $\omega\mapsto\omega'$ changes only those bits. Conditioning on the bits outside
$B(x,M)$ and comparing pointwise on the finite product gives
\[
\Pp(\mathrm{Bad}_K)\le(K+d+1)(dM)^{K+d}\vartheta^{K+d}\,\Pp(O_K).
\]
\end{itemize}
The sequential reconstruction replaces the observation of~\cite[Section~3]{OAINU} that every changed
edge is incident to $B\subseteq C'_x$: after pruning, $B\setminus B''$ and some contacts can leave
$C'_x$.

\paragraph{Summation.} By Lemma~\ref{lem:radius} with $\kappa_0=1/(2d)$ and $\kappa=K/(2d)$,
\[
\Pp(\mathrm{Bad}_K)\le\exp\Bigl(C_1(K+d)\log M-\frac{cK^2M^{2\eps}}{4d^2\log M}\Bigr),
\]
with $C_1$ depending on $d$ and $p_c$. As $K\ge1$, $K+d\le(d+1)K$, and the exponent is at most
$-cK^2M^{2\eps}/(8d^2\log M)$ as soon as $M^{2\eps}/(\log M)^2\ge8d^2(d+1)C_1/c$, uniformly in $K\ge1$.
Summing over the fewer than $M$ values of $K$,
\[
\Pp(\mathrm{Bad})\le M\exp\bigl(-cM^{2\eps}/(8d^2\log M)\bigr)\le e^{-M^\eps}
\]
for all sufficiently large $M$, uniformly in $x$.

\paragraph{Locality.} Explore $C_x$ breadth-first by site queries: query $x$, then unqueried
neighbours of discovered open vertices; stop when the cluster is exhausted or more than $M$ (that is,
$\lfloor M\rfloor+1$) open vertices are found. While at most $M$ open vertices are known they form a
connected set containing $x$, so they lie in $B(x,M-1)$ and every queried vertex lies in $B(x,M)$. If
$x$ is closed, $C_x=\varnothing$, which is good. If the cluster is exhausted, its vertex set is known,
and goodness depends only on that set and on $G$. If more than $M$ open vertices are found, $s_x\le M$
fails. So $\{s_x\le M,\ C_x\text{ good for cap }M\}$ is determined by the bits in $B(x,M)$.
\qed