US-EGMO-TST 2019 Problem 1

A $3 \times 3$ grid of unit cells is given. A snake of length $k$ is an animal which occupies an ordered $k$ -tuple of cells in this grid, say $(s_1, \dots, s_k)$ . These cells must be pairwise distinct, and $s_i$ and $s_{i+1}$ must share a side for $i = 1, \dots, k-1$ . After being placed in a finite $n \times n$ grid, if the snake is currently occupying $(s_1, \dots, s_k)$ and $s$ is an unoccupied cell sharing a side with $s_1$ , the snake can move to occupy $(s, s_1, \dots, s_{k-1})$ instead. The snake has turned around if it occupied $(s_1, s_2, \dots, s_k)$ at the beginning, but after a finite number of moves occupies $(s_k, s_{k-1}, \dots, s_1)$ instead.

Find the largest integer $k$ such that one can place some snake of length $k$ in a $3 \times 3$ grid which can turn around.