좀비 울타리 짓기

$n \times n$ 크기의 땅 격자가 주어집니다. 격자점(격자의 꼭짓점)을 잇는 선을 따라 울타리(벽)를 세워, 모든 벽이 교차나 분기 없이 하나의 닫힌 고리(단순 순환 하나)를 이루도록 만들어야 합니다. 즉, 모든 격자점에는 벽이 $0$개 또는 정확히 $2$개만 닿아야 합니다.

일부 칸에는 숫자($0$, $1$, $2$, $3$)가 적혀 있으며, 그러한 칸은 네 변에 정확히 그 숫자만큼의 벽으로 둘러싸여야 합니다. 숫자가 없는 칸은 아무런 제약도 주지 않습니다.

예를 들어, 다음과 같은 $5 \times 5$ 격자가 주어지면:

다음과 같은 울타리를 만들 수 있습니다:

격자는 항상 $n \times n$이며 $1 \le n \le 6$이고, 각 칸은 숫자($0$, $1$, $2$, $3$) 또는 빈칸입니다. 모든 숫자 제약을 만족하는 가장 긴 고리의 길이 — 즉 고리가 지나는 격자점의 개수 — 를 출력하거나, 유효한 고리가 없으면 $-1$을 출력합니다. 길이가 $0$인 고리는 유효하지 않으며, 유효한 고리는 $0$이 아닌 넓이를 둘러싸야 합니다.

입력은 여러 개의 울타리 퍼즐로 이루어집니다. 각 퍼즐은 보드의 크기 $n$ ($1 \le n \le 6$)을 담은 줄로 시작하고, 이어서 각 줄에 $n$개의 문자가 들어있는 $n$개의 줄로 격자를 나타냅니다. 각 문자는 해당 칸의 벽 개수를 나타내는 숫자 0–3, 또는 제약이 없는 칸을 나타내는 -입니다. 각 퍼즐 뒤에는 빈 줄이 따릅니다. 입력의 끝은 $0$ 하나만 있는 줄로 표시됩니다.

각 퍼즐에 대해, 모든 제약을 지키면서 만들 수 있는 가장 긴 울타리 고리의 길이를 한 줄에 출력하고, 그러한 고리가 없으면 $-1$을 출력합니다. 답 사이를 구분하는 줄바꿈 외에는 불필요한 공백을 출력하지 않습니다.