gain intuition for the definition of $T_i(v)$ and $R_i(v)$, consider the set $G_i(v)$ of all vertices $s \in V(G)$ such that $d(v,s) \le R/2$ and $d(s, t) \le 3R/2 \text{ for all } t\in \bigcup_{0 \le j \le i-1}{R_{j}(v)}$. We remark that our algorithm does not compute $G_i(v)$, but its definition is essential for the analysis. Intuitively, the set $G_i(v)$ consists of the vertices after $i$ rounds that the algorithm still believes could be in a cycle of length $R$ with $v$. If $|G_i(v)| \ge 100\sqrt{n}\log n$, then by the choice of $S_i$ as an independent random set of expected size $O(\sqrt{n})$, we have that $T_i(v)$ is a random sample of $G_i(v)$ of expected size at least $100\log n.$ In this way, $R_i(v)$ is just a random sample of $G_i(v)$ of size $O(\log n).$

As we show in \[lem:SubsetShrinks\], if $|G_M(v)| \ge 100\sqrt{n}\log n$, our algorithm discovers w.h.p. a cycle of length at most $3R$ sometime during the shortest path computations done at the beginning. On the other hand, if $|G_M(v)| \le 100\sqrt{n}\log n$, then we can grow a shortest path tree from $v$ but only include vertices in $G_M(v)$ to search for a cycle of length $R$, only paying 